米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 プログラム変換装置およびプログラム変換方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−121378
公開日 平成7年(1995)5月12日
出願番号 特願平5−265050
出願日 平成5年(1993)10月22日
代理人 【弁理士】
【氏名又は名称】中島 司朗
発明者 高山 秀一 / 富永 宣輝 / 田中 旭
要約 目的
コンパイラのループ処理に存在する線形演算式を書き換えるにあたって、ループ処理外に同一の線形演算式が存在すればその線形演算式をも書き換える。

構成
ループ内誘導変数検出部14は、ループ内に存在する線形演算式のコードを検出する。ループ外誘導変数検出部15は、ループ内誘導変数検出部14が検出した線形演算式のコードと同一の線形演算式のコードを検出する。ループ内誘導変数書換部16が、ループ内誘導変数検出部14が検出した線形演算式のコードを、増分値が正又は負の値である加算式のコードに書き換える。更にループ外誘導変数書換部19が、ループ外誘導変数検出部15が検出した線形演算式のコードを、ループ内誘導変数検出部14が書き換えた加算式のコードに書き換える。
特許請求の範囲
【請求項1】プログラム保持部に保持されている処理対象のプログラムのループ処理内の制御変数を含む演算式の演算結果の増分値を求め、その増分値だけ中身が増加する新たな変数を作成し、新たな変数および増分値を被演算子とする加算式を作成し、その加算式の演算結果が新たな変数に代入される代入文を作成して、前記演算式を新たな変数に書き換え、更にループ処理外の前記制御変数を含む演算式を新たな変数に書き換えるプログラム変換装置であって、プログラム保持部に保持されているプログラムのループ処理内から、制御変数が被演算子として使用され、他の演算子に、定数あるいはループ処理内で不変な変数が使用されている演算式を検出するループ内演算式検出手段と、前記ループ内演算式検出手段が検出した演算式が含まれるループ処理の外部から、同一の演算式を検出し、更に当該演算式において被演算子として使用されている変数が、ループ処理からループ処理の外部の演算式までの領域内に定義されているか否かを判定して、定義されていないと判定すれば、検出した演算式は書き換え可能であると判定し、定義されていると判定すれば、検出した演算式は書き換え不可能であると判定するループ外演算式検出手段と、前記制御変数の、一回のループ処理における増分値に基づいて、前記ループ内演算式検出手段が検出した演算式の、1回の演算の実行による演算結果の増分値を算出する増分値算出手段と、前記プログラム保持部に保持されているプログラム中で、使用されてない変数名の変数を作成する変数作成手段と、前記変数作成手段が作成した変数と、前記増分値算出手段が算出した増分値とを加算し、加算した結果を当該変数に代入する代入文を作成する代入文作成手段と、プログラム中の制御変数の値を更新する代入文を、前記代入文作成手段が作成した代入文に書き換え、前記ループ内演算式検出手段が検出した箇所の演算式を、前記変数作成手段が作成した変数に書き換えるループ内演算式書き換え手段とループ外演算式検出手段が、書き換え可能であると判定した場合、前記ループ外演算式検出手段が検出した箇所の演算式を、前記変数作成手段が作成した変数に書き換えるループ外演算式書き換え手段とを備えることを特徴とするプログラム変換装置。
【請求項2】プログラム保持部に保持されている処理対象のプログラムのループ処理内の制御変数を含む演算式の演算結果の増分値を求め、その増分値だけ中身が増加する新たな変数を作成し、新たな変数および増分値を被演算子とする加算式を作成し、その加算式の演算結果が新たな変数に代入される代入文を作成して、前記演算式を新たな変数に書き換え、更にループ処理外の前記制御変数を含む演算式を新たな変数に書き換えるプログラム変換方法であって、プログラム保持部に保持されているプログラムのループ処理内から、制御変数が被演算子として使用され、他の演算子に、定数あるいはループ処理内で不変な変数が使用されている演算式を検出するループ内演算式検出ステップと、前記ループ内演算式検出ステップが検出した演算式が含まれるループ処理の外部から、同一の演算式を検出し、更に当該演算式において被演算子として使用されている変数が、ループ処理からループ処理の外部の演算式までの領域内に定義されているか否かを判定して、定義されていないと判定すれば、検出した演算式は書き換え可能であると判定し、定義されていると判定すれば、検出した演算式は書き換え不可能であると判定するループ外演算式検出ステップと、前記制御変数の、一回のループ処理における増分値に基づいて、前記ループ内演算式検出ステップが検出した演算式の、1回の演算の実行による演算結果の増分値を算出する増分値算出ステップと、前記プログラム保持部に保持されているプログラム中で、使用されてない変数名の変数を作成する変数作成ステップと、前記変数作成ステップが作成した変数と、前記増分値算出ステップが算出した増分値とを加算し、加算した結果を当該変数に代入する代入文を作成する代入文作成ステップと、プログラム中の制御変数の値を更新する代入文を、前記代入文作成ステップが作成した代入文に書き換え、前記ループ内演算式検出ステップが検出した箇所の演算式を、前記変数作成ステップが作成した変数に書き換えるループ内演算式書き換えステップと ループ外演算式検出ステップが、書き換え可能であると判定した場合、前記ループ外演算式検出ステップが検出した箇所の演算式を、前記変数作成ステップが作成した変数に書き換えるループ外演算式書き換えステップとからなることを特徴とするプログラム変換装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、ソースコードを対象コードに変換するコンパイラ等に適用され、ループ処理内で用いられる誘導変数についてコードの最適化を行うプログラム変換装置、およびプログラム変換方法に関する。
【0002】
【従来の技術】コンパイラ等によってプログラムのソースコードを対象コードに変換する際などには、多くの場合、対象コードのサイズの低減や実行速度の向上等を目的として種々の最適化処理が行われ、そのうちのひとつとして誘導変数の最適化が行われることもある。上記誘導変数は、例えば「コンパイラII」(A.Vエイホ R.セシィ J.D.ウルマン共著、原田賢一訳:サイエンス社)に記載されているように、ループ処理において、1回のループが繰り返されるごとに値が正又は負の一定量ずつ増加する変数のことで、その最適化とは、例えばソースコードにおいてループ処理の制御変数に所定の数を乗算して値を得る誘導変数が用いられている場合、前回のループ処理における誘導変数の値に上記所定の数を加算して新たな値を得るコードを生成することなどにより、処理速度の向上やコードサイズの低減を図ることである。
【0003】誘導変数の最適化は、データ処理を行うために記述された、膨大な要素を持つ配列の各要素に数値を格納するようなループ処理に対して特に有効である。何故なら配列の各要素にデータを格納するような記述を機械語プログラムに翻訳する場合、コンパイラは、各要素のアドレスを計算する必要があり、その各要素のアドレスの計算には、各要素のサイズの大きさと、それぞれの要素の順位を示す制御変数との乗算が行われるからである。一般に機械語命令の乗算命令は加算命令より実行時間が長いため、このような乗算を加算に置き換えると、上述のループ処理が機械語に置き換えられたときの処理速度は一段と向上する。
【0004】なお、コンパイラ等における上記のような誘導変数の最適化はプログラム変換装置を用いて行われる。プログラム変換装置について説明する前に、使用する用語について以下に説明する。
・制御変数ループ処理を続けるか、中止するかの判定を行うために使用され、ループ処理が一回行われる度に一定の値だけ増加する変数である。
・演算式変数、定数を被演算子とする式である。(例えば、100*x+2、x/200+10)
・代入文等号の左側に変数が存在し、また右側に変数、定数、演算式が存在して、等号の左側の変数に、等号の右側の内容を代入する文である。(例えば、y=130、y=100*x+2、y=x/200+10)
・線形演算式変数が被演算子として使用されている演算式で、全ての変数の次数が1であるものをいう。(例えば、100*x+2 x/200+10)
・変数の定義代入文によって、変数の値を設定することである。(例えば、a=100、s=100*2)
・変数の使用演算式の被演算子に変数を使用することである。
【0005】図3はC言語のコンパイラに備えられる従来のプログラム変換装置の構成を示す図である。プログラム変換装置は、誘導変数保持部21と、ループ内誘導変数検出部22と、ループ内誘導変数書換部23とで構成される。誘導変数保持部21は、ループ内の線形演算式、誘導変数の変数名、1ループ処理ごとの増分値、および初期値を保持する。
【0006】ループ内誘導変数検出部22は、プログラム中のループ処理内の演算に対して線形演算式検出動作を行い、線形演算式検出動作によって検出された演算で定義されている変数を誘導変数とし、誘導変数と、その誘導変数に関する情報とを誘導変数保持部21に保持させる。線形演算式検出動作について具体的に述べる。線形演算式検出部22は、プログラム中のそれぞれのループ処理において、そのループ処理が一回実行される度毎に実行される演算を検出し、その演算式が、制御変数と定数とを被演算子とする演算式であるか、あるいは、制御変数と変数とを被演算子とする演算式であるかを調べる(演算式は、制御変数と、変数と、定数とを被演算子とする演算式であってもよい。)。もし他方の被演算子が変数であれば、その変数の定義が、ループ処理内に存在するか否かを調べる。このような調査の結果、一方の被演算子が制御変数であり、他方の被演算子が定数あるいはループ処理内で値が不変の変数であれば、誘導変数検出部22は、その演算式が線形演算式であるか否かを調べる。もしループ内誘導変数検出部22が線形演算式を検出すれば、その線形演算式が存在した箇所を記憶し、その線形演算式によって定義されている変数を誘導変数とする。このようにしてループ内誘導変数検出部22が誘導変数を求め、誘導変数保持部21に保持させたあと、ループ内誘導変数検出部22は、線形演算式検出動作によって検出された線形演算式の、1回のループ処理による演算結果の増分値を算出する。ここで増分値は、正の値でも負の値でもよい。線形演算式の演算結果の増分値を求めた後、ループ内誘導変数検出部22は、誘導変数の初期値を求めて誘導変数保持部21に保持させる。
【0007】ループ内誘導変数書換部23は、定義書換部24と、判定条件書換部25とで構成される。定義書換部24は、ループ処理内の誘導変数の定義を書き換える。具体的には、定義書換部24は、検出した線形演算式に乗算、除算が含まれており、書き換え有効であるか否かを判定する。もし書き換え有効であると判定すると、書き換えのために使用できる変数を生成し、その変数を、ループ内誘導変数検出部22が求めた増分値だけ増加させる加算式のコードを作成し、新たに生成した変数が作成した加算式のコードで定義される代入文を、プログラムのループ処理内の所定の位置に書き込む。書き込み後、定義書換部24は、プログラムの、ループ内誘導変数検出部22が検出した箇所の線形演算式を、変数に書き換える。
【0008】判定条件書換部25は、制御変数が、ループ処理外で、他の変数を定義するために使用されているか否かを確認し、もし使用されていなければ、制御変数によって行われていたループ処理を続けるか終了するかの判定を、新たな変数が行うようにし、制御変数する初期化する代入文のコードと、制御変数の内容を増加させている代入文のコードと、制御変数が判定を行っている代入文のコードとをループ処理から消去する。
【0009】尚、上述の初期化コードを作成する構成、判定を書き換える構成の詳細については、本発明の主眼でないので説明を省略する。以上のように構成されたプログラム変換装置の動作について、説明する。図4(a)は、各要素の大きさがワード型(2バイト)である配列a〔〕の各要素(a〔0〕〜a〔98〕)に、0が代入されるように、C言語で記述されたプログラムである。
【0010】プログラム変換装置を備えたコンパイラは、プログラム中の配列についての記述を書き換える。書き換えた結果を図4(b)に示す。配列の書き換えは、本発明の主眼ではないので説明を省略するが、書き換えられた箇所について説明しておく。変数s1は、配列の各要素のアドレスを指示するためのポインタ変数である。ポインタ変数s1は、配列のため確保されている領域のメモリ上の先頭のアドレスから、それぞれの要素のアドレスへのオフセット値を足して計算される。図中の「s1=&a+2*i」は、配列の各要素のアドレスを計算し、計算結果をポインタ変数s1に代入する代入文である。この代入文において、&aは、上述の配列a〔〕の先頭のアドレスであり、2は、配列a〔〕の各要素のバイトサイズを示す。更に変数iは、それぞれの要素の順位を示す制御変数である。次の行の「*s1=0」は、ポインタ変数s1が指示するアドレスのメモリに0を格納するためのコードである。このように配列の記述が書き換えられたプログラムに対して、上述のプログラム変換装置が作動する。ループ内誘導変数検出部22が線形演算式検出動作を行い、線形演算式のコードである「&a+2*i」を検出して、変数s1を誘導変数として誘導変数保持部21に保持させる。更にループ内誘導変数検出部22は、線形演算式「&a+2*i」の演算結果の増分値を求める。ループ内誘導変数検出部22は、制御変数iの内容を増加する代入文のコードである「i=i+1」を参照して、制御変数iの増分値である1を求め、「&a+2*i」の増分値である2を算出する。次に定義書換部24は、線形演算式の書き換えのために使用できる変数である変数tを生成し、変数tが、2だけ加算されるような加算式のコードである「t=t+2」を作成して、プログラム中の所定の位置に書き込み、プログラム中の、線形演算式のコードである「&a+2*i」が記述されている箇所を、変数tに書き換える。その結果、代入文「s1=&a+2*i」は、「s1=t」に書き換えられる。更に定義書換部24は、変数tの内容を初期化するコードである「t=&a」を作成し、これらをプログラム中の所定の位置に書き込む。判定条件書換部25は、ループ外で、制御変数iが、他の変数を定義するために使用されているか否かを確認し、もし使用されていなければ、制御変数iによって行われていたループ処理を続けるか終了するかの判定を、変数tが行うようにし、制御変数iを初期化する代入文のコードと、制御変数iの内容を増加させる代入文のコードと、制御変数iがループ処理の判定を行う代入文のコードとをループ処理から消去する。その結果、図4(b)に示したプログラムは、図4(c)に示すように、ループ処理が変数tによって制御されるように書き換えられる。
【0011】
【発明が解決しようとする課題】しかしながら上記従来技術によれば、ループ処理の外部に存在する演算式において、そのループ処理の制御変数が被演算子として使用されている場合、プログラム変換装置は、ループ処理内の制御変数の内容を増加させている代入文のコードを消去することができず、ループ処理が機械語に置き換えられたときの処理速度の高速化が充分に達成できないという問題点があった。
【0012】例えば、図5(a)は、ループ処理によって、配列a〔〕のa〔0〕〜a〔998〕までの要素に0が代入され、配列の最後の要素であるa〔999〕に、1が代入されるように記述されたプログラムである。このようなプログラムに対してプログラム変換装置が、上述の書き換えの動作を行う場合、プログラム変換装置は、a〔999〕のアドレスを求めるためにループ処理終了時に999という数値を格納しているはずの制御変数iを消去しないで、ループ処理内に、制御変数iを使用したコードを残したまま処理を終了する。つまりプログラム変換装置は、図5(b)のようにプログラムについて、線形演算式「s1=&a+2*i」のコードが行う計算を、加算文「t=t+2」のコードで代用するように書き換えておきながらも、制御変数iの内容を増加させている代入文のコードを消去することができず、図5(c)の状態で処理を終了する。このプログラムは処理を999回繰り返して行うプログラムであるから、プログラム変換装置によるプログラムの書き換え後、コンパイラによって最終的に生成される機械語プログラムは、その冗長な線形演算式のコードに該当する機械語命令を999回繰り返して行う。その結果、機械語命令の実行時間は必要以上に長くなる。
【0013】本発明は上記問題点に鑑み、ループ処理外で他の変数の定義に使用されている誘導変数をも対象とし、プログラム処理の高速化を実現するプログラム変換装置を提供することを目的とする。
【0014】
【課題を解決するための手段】上記課題を解決するために本発明のプログラム変換装置は、プログラム保持部に保持されている処理対象のプログラムのループ処理内の制御変数を含む演算式の演算結果の増分値を求め、その増分値だけ中身が増加する新たな変数を作成し、新たな変数および増分値を被演算子とする加算式を作成し、その加算式の演算結果が新たな変数に代入される代入文を作成して、前記演算式を新たな変数に書き換え、更にループ処理外の前記制御変数を含む演算式を新たな変数に書き換えるプログラム変換装置であって、プログラム保持部に保持されているプログラムのループ処理内から、制御変数が被演算子として使用され、他の演算子に、定数あるいはループ処理内で不変な変数が使用されている演算式を検出するループ内演算式検出手段と、前記ループ内演算式検出手段が検出した演算式が含まれるループ処理の外部から、同一の演算式を検出し、更に当該演算式において被演算子として使用されている変数が、ループ処理からループ処理の外部の演算式までの領域内に定義されているか否かを判定して、定義されていないと判定すれば、検出した演算式は書き換え可能であると判定し、定義されていると判定すれば、検出した演算式は書き換え不可能であると判定するループ外演算式検出手段と、前記制御変数の、一回のループ処理における増分値に基づいて、前記ループ内演算式検出手段が検出した演算式の、1回の演算の実行による演算結果の増分値を算出する増分値算出手段と、前記プログラム保持部に保持されているプログラム中で、使用されてない変数名の変数を作成する変数作成手段と、前記変数作成手段が作成した変数と、前記増分値算出手段が算出した増分値とを加算し、加算した結果を当該変数に代入する代入文を作成する代入文作成手段と、プログラム中の制御変数の値を更新する代入文を、前記代入文作成手段が作成した代入文に書き換え、前記ループ内演算式検出手段が検出した箇所の演算式を、前記変数作成手段が作成した変数に書き換えるループ内演算式書き換え手段とループ外演算式検出手段が、書き換え可能であると判定した場合、前記ループ外演算式検出手段が検出した箇所の演算式を、前記変数作成手段が作成した変数に書き換えるループ外演算式書き換え手段とを備えている。
【0015】また、本発明のプログラム変換方法は、プログラム保持部に保持されている処理対象のプログラムのループ処理内の制御変数を含む演算式の演算結果の増分値を求め、その増分値だけ中身が増加する新たな変数を作成し、新たな変数および増分値を被演算子とする加算式を作成し、その加算式の演算結果が新たな変数に代入される代入文を作成して、前記演算式を新たな変数に書き換え、更にループ処理外の前記制御変数を含む演算式を新たな変数に書き換えるプログラム変換方法であって、プログラム保持部に保持されているプログラムのループ処理内から、制御変数が被演算子として使用され、他の演算子に、定数あるいはループ処理内で不変な変数が使用されている演算式を検出するループ内演算式検出ステップと、前記ループ内演算式検出ステップが検出した演算式が含まれるループ処理の外部から、同一の演算式を検出し、更に当該演算式において被演算子として使用されている変数が、ループ処理からループ処理の外部の演算式までの領域内に定義されているか否かを判定して、定義されていないと判定すれば、検出した演算式は書き換え可能であると判定し、定義されていると判定すれば、検出した演算式は書き換え不可能であると判定するループ外演算式検出ステップと、前記制御変数の、一回のループ処理における増分値に基づいて、前記ループ内演算式検出ステップが検出した演算式の、1回の演算の実行による演算結果の増分値を算出する増分値算出ステップと、前記プログラム保持部に保持されているプログラム中で、使用されてない変数名の変数を作成する変数作成ステップと、前記変数作成ステップが作成した変数と、前記増分値算出ステップが算出した増分値とを加算し、加算した結果を当該変数に代入する代入文を作成する代入文作成ステップと、プログラム中の制御変数の値を更新する代入文を、前記代入文作成ステップが作成した代入文に書き換え、前記ループ内演算式検出ステップが検出した箇所の演算式を、前記変数作成ステップが作成した変数に書き換えるループ内演算式書き換えステップと ループ外演算式検出ステップが、書き換え可能であると判定した場合、前記ループ外演算式検出ステップが検出した箇所の演算式を、前記変数作成ステップが作成した変数に書き換えるループ外演算式書き換えステップとからなる。
【0016】
【作用】上記の手段により本発明のプログラム変換装置(方法)において、ループ内演算式検出手段(ステップ)は、プログラム保持部に保持されているプログラムのループ処理内から、制御変数が被演算子として使用されている演算式を検出する。検出した演算式が含まれるループ処理の外部に対して、ループ外演算式検出手段(ステップ)が作動し、前記ループ内演算式検出手段(ステップ)が検出した演算式と、同一の演算式を検出し、更に当該演算式において被演算子として使用されている変数が、ループ処理からループ処理の外部の演算式までの領域内に定義されているか否かを判定する。前記制御変数の、一回のループ処理における増分値に対して、増分値算出手段(ステップ)が作動し、前記ループ内演算式検出手段(ステップ)が検出した演算式の、1回の演算の実行による演算結果の増分値が算出される。前記プログラム保持部に保持されているプログラム中に対して、変数作成手段(ステップ)が作動し、使用されてない変数名の変数が、使用可能な変数として作成される。前記変数作成手段(ステップ)が作成した変数と、前記増分値算出手段(ステップ)が算出した増分値とに対して、代入文作成手段(ステップ)が作動し、前記変数作成手段(ステップ)が作成した変数と、前記増分値算出手段(ステップ)が算出した増分値とを加算した結果が当該変数に代入される代入文が作成される。プログラム中の制御変数の値を更新する代入文と、前記代入文作成手段(ステップ)が作成した代入文とに対して、前記ループ内演算式検出手段(ステップ)が作動し、検出した箇所の演算式が、前記変数作成手段(ステップ)が作成した変数に書き換えられ、前記ループ内演算式検出手段(ステップ)が検出した箇所の演算式が、前記変数作成手段(ステップ)が作成した変数に書き換えられる。前記ループ外演算式検出手段(ステップ)が書き換え可能であると判定すると、前記ループ外演算式検出手段(ステップ)が検出した箇所の演算式に対して、ループ外演算式書き換え手段(ステップ)が作動し、前記ループ外演算式検出手段(ステップ)が検出した箇所の演算式が前記変数作成手段(ステップ)が作成した変数に書き換えられる。
【0017】
【実施例】図1はプログラム変換装置の構成を示す図である。このプログラム変換装置による誘導変数の最適化は、例えばコンパイラに与えられるソースコードに対して行われるようにしてもよいし、また、コンパイラによるコンパイル処理の途中で得られる中間コードなどに対して行われるようにしてもよい。
【0018】プログラム変換装置は、制御部11と、最適化前コード保持部12と、誘導変数保持部13と、ループ内誘導変数検出部14と、ループ外誘導変数検出部15と、ループ内誘導変数書換部16と、ループ内誘導変数書換部16と、ループ外誘導変数書換部19とで構成される制御部11は、プログラム変換装置はプログラムのプログラム変換処理の全体を制御する。
【0019】最適化前コード保持部12は、処理対象である元のプログラムを保持する。誘導変数保持部13は、最適化前コード保持部12に保持されているプログラム中のループ処理内の線形演算式のコード、誘導変数の変数名、1ループ処理ごとの増分値、および初期値を保持する。ループ内誘導変数検出部14は、最適化前コード保持部12に保持されているプログラムの、何れかのループ処理内に存在する演算に対して線形演算式検出動作を行い、(線形演算式検出動作は、従来技術として既に説明しているので詳細な説明は省略する。)線形演算式検出動作によって検出された演算式で定義されている変数を誘導変数とし、誘導変数と、その誘導変数に関する情報とを誘導変数保持部13に保持させる。もしループ内誘導変数検出部14が線形演算式を検出すれば、ループ内誘導変数検出部14は、その線形演算式が存在していた箇所を記憶し、その線形演算式によって定義されている変数を誘導変数とする。このようにして誘導変数を求め、誘導変数保持部21に保持させたあと、ループ内誘導変数検出部14は、線形演算式検出動作によって検出された線形演算式の演算結果の増分値を算出する。ここで増分値は、正の値でも負の値でもよい。線形演算式の増分値を算出した後、ループ内誘導変数検出部14は、誘導変数の初期値を求めて誘導変数保持部21に保持させる。
【0020】ループ外誘導変数検出部15は、最適化前コード保持部12に保持されているプログラムの、ループ内誘導変数検出部14が演算式を検出したループ処理の外部から、ループ内誘導変数検出部14が検出した演算式と同一の演算式を探索し、もし存在すれば、その演算が存在する箇所を記憶する。記憶後、ループ外誘導変数検出部15は、プログラム中の、ループ処理から検出したループ処理の外部の演算式までの領域において、その演算式で被演算子として使用されている変数(制御変数あるいはループ処理内で不変な変数)が定義されているか否かを判定する。定義されていなければ、ループ外誘導変数検出部15は、探索した演算式は書き換え可能であると判定し、定義されていれば、探索した演算式は書き換え不可能であると判定する。例えば、最適化前コード保持部12に保持されているプログラムのループ処理内に「s1=i*3」という代入文のコードが存在し、そのループ処理の外部に「s1=i*3」という代入文のコードと、「w3=i*3」という代入文のコードとが存在する場合、何れの代入文の演算式のコードをも、ループ外誘導変数検出部15は検出し、それらの演算式が存在する箇所を記憶する。また、最適化前コード保持部12に保持されているプログラムのループ処理内に「s1=s*i」という代入文のコードが存在し、そのループ処理の外部に「s4=s*i」という代入文のコードが存在して、ループ処理から検出したループ処理の外部の演算式「s4=s*i」までの領域に、「s=3」という代入文のコードが存在する場合、ループ外誘導変数検出部15は、「s4=s*i」というコードと、「s=3」というコードとを検出する。
【0021】ループ内誘導変数書換部16は、定義書換部17と、判定条件書換部18とで構成される。定義書換部17は、最適化前コード保持部12に保持されているプログラムの、ループ処理内の線形演算式の定義の書き換えを行う。具体的には、ループ内誘導変数検出部14が検出した線形演算式に乗算、除算が含まれており書き換え有効であるか否かを判定する。もし書き換え有効であると判定したならば、定義書換部17は、書き換えのために使用できる変数を生成し、その変数を、ループ内誘導変数検出部14が算出した、線形演算式の増分値だけ増加させる加算式のコードを作成して、最適化前コード保持部12に保持されているプログラムの、ループ処理内の所定の位置に書き込む。書き込み後、定義書換部17は、最適化前コード保持部12に保持されているプログラムの、ループ内誘導変数検出部14が検出した箇所の線形演算式を、変数に書き換える。更に定義書換部17は、誘導変数保持部13に保持されている誘導変数の初期値を参照して、加算式コードで使用した変数を初期化する代入文のコードを作成し、プログラムのループ処理内の所定の位置に書き込む。
【0022】判定条件書換部18は、新たな変数がループ処理を続けるか終了するかの判定を行うように最適化前コード保持部12に保持されているプログラムのループ処理を書き換える。更に制御変数の初期化する代入文のコードと、制御変数の内容を増加させている代入文のコードと、制御変数が判定を行うコードとを、最適化前コード保持部12に保持されているプログラムのループ処理から消去する。
【0023】ループ外誘導変数書換部19は、ループ外誘導変数検出部15が書き換え可能と判定した場合、最適化前コード保持部12に保持されているプログラムの、ループ外誘導変数検出部15が検出した箇所の線形演算式を、定義書換部17が生成した変数に書き換える。例えば、定義書換部17が「s1=3*i」という代入文のコードを「s1=t」に書き換えており、ループ外誘導変数検出部15が「s2=3*i」という代入文のコードを検出したとすると、ループ外誘導変数書換部19は、「s2=3*i」のコードを「s2=t」に書き換える。
【0024】尚、上述の初期化コードを作成する構成、判定を書き換える構成の詳細については、本発明の主眼でないので説明を省略する。以上のように構成されたプログラム変換装置の動作について、説明する。図3(a)は、各要素の大きさがワード型(2バイト)である配列a〔〕の各要素(a〔0〕〜a〔98〕)に、0を代入し、配列の最後の要素であるa〔99〕に、終値として1が代入されるようにC言語で記述されたプログラムである。
【0025】プログラム変換装置を備えたコンパイラは、プログラム中の配列についての記述を一旦書き換える。書き換えた結果を図3(b)に示す。このように配列の記述が書き換えられたプログラムに対して、上述のプログラム変換装置が作動する。先ず、制御部11は、ループ内誘導変数検出部14を起動する。ループ内誘導変数検出部14は線形演算式検出動作を行い、「&a+2*i」を検出して、変数s1を誘導変数として最適化前コード保持部12に保持させる。ループ内誘導変数検出部14は、これらの線形演算式についての演算結果の増分値を求める。つまり、ループ内誘導変数検出部14は、制御変数iの値を増加している代入文のコードである「i=i+1」を参照して、制御変数iの増分値である1を求め、線形演算式が1回実行されることによる線形演算式「&a+2*i」の増分値である2を算出する。次にループ外誘導変数検出部15が、ループ内誘導変数検出部14が演算式を検出したループ処理の外部から、ループ内誘導変数検出部14が検出した演算式である「&a+2*i」と同一の演算式が等号の右側に存在する代入文である「s1=&a+2*i」を検出する。検出後、制御部11は、ループ外誘導変数検出部15を起動する。ループ外誘導変数検出部15は、最適化前コード保持部12内の、その演算式が存在する箇所を記憶する。次に制御部11は、定義書換部17を起動する。定義書換部17は、書き換えのために使用可能な変数である変数tを生成し、変数tが、2だけ加算されるような加算式のコードである「t=t+2」を作成して、プログラム中の所定の位置に書き込み、プログラム中の線形演算式のコードである「&a+2*i」を、変数tに書き換える。更に定義書換部17は、変数tの内容を初期化するコードである「t=&a」を作成し、これらをプログラム中の所定の位置に書き込む。次に制御部11は、判定条件書換部18を起動する。判定条件書換部18は、制御変数iによって行われていたループ処理を続けるか終了するかの判定を、変数tが行うようにし、元の誘導変数iの初期化する代入文のコードと、制御変数iの内容を増加させている代入文のコードと、制御変数iが判定を行っている代入文のコードとをループ処理内から消去する。次に制御部11は、ループ外誘導変数書換部19を起動する。ループ外誘導変数書換部19は、ループ外誘導変数検出部15が検出した箇所の線形演算式「&a+2*i」を、定義書換部17が生成した変数tに書き換える。その結果、図5(b)に示したプログラムは、ループ処理が変数tによって制御されるように書き換えられる。書き換えた結果を図5(c)に示す。
【0026】
【発明の効果】以上説明してきたように本発明のプログラム変換装置によれば、制御変数が、そのループ処理の外部に存在する演算式において、そのループ処理の制御変数が被演算子として使用されていても、そのループ処理の外部に存在する演算式が、ループ内に存在するものと同一ならば、その外部の演算式をも書き換えることができるので、ループ処理内の制御変数の内容を増加させている代入文のコードを消去することができ、ループ処理が機械語に置き換えられたときの処理速度の高速化が充分に達成できるという効果がある。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013