米国特許情報 | 欧州特許情報 | 国際公開(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−36707
公開日 平成7年(1995)2月7日
出願番号 特願平5−181493
出願日 平成5年(1993)7月22日
代理人 【弁理士】
【氏名又は名称】中島 司朗
発明者 高山 秀一 / 入交 旬子 / 湯川 博司
要約 目的
誘導変数を含むプログラムコードの処理速度の向上やコードサイズの低減を図る。

構成
誘導変数検出手段12は最適化前コード記憶手段11に記憶されているコードに含まれる誘導変数を検出して誘導変数保持手段13に登録し、定義文削除手段14aは各誘導変数の値が使用される使用文を検出し、検出された使用文が、唯一の、誘導変数の値を定義する文である場合に、先の誘導変数の値の定義文を削除し、変換抑制手段14bは同様に誘導変数の値が使用される使用文を検出し、検出された使用文が、複数の、他の誘導変数の値を定義する文である場合に、それらの複数の誘導変数の登録を誘導変数保持手段13から削除し、コード変換手段15は誘導変数保持手段13に登録されている誘導変数の値の定義文を、誘導変数の値と増分値を加算して新たな値を定義する文に変換する。
特許請求の範囲
【請求項1】 プログラムコードのループ処理中で用いられる誘導変数を検出する検出手段と、検出された誘導変数を示す情報を保持する保持手段と、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換手段と、検出手段で検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードを削除する削除手段とを有することを特徴とするプログラム変換装置。
【請求項2】 プログラムコードのループ処理中で用いられる誘導変数を検出する検出手段と、検出された誘導変数を示す情報を保持する保持手段と、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換手段と、検出手段で検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換手段によるコードの変換を抑制する変換抑制手段とを有することを特徴とするプログラム変換装置。
【請求項3】 上記変換抑制手段は、検出手段で検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数を示す情報を保持手段から削除するように構成されていることを特徴とする請求項2のプログラム変換装置。
【請求項4】 請求項1の検出手段、保持手段、変換手段、および削除手段と、請求項2の変換抑制手段とを有することを特徴とするプログラム変換装置。
【請求項5】 プログラムコードのループ処理中で用いられる誘導変数を検出する検出ステップと、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換ステップと、検出ステップで検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードを削除する削除ステップとを有することを特徴とするプログラム変換方法。
【請求項6】 プログラムコードのループ処理中で用いられる誘導変数を検出する検出ステップと、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換ステップと、検出ステップで検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換ステップの実行を抑制する変換抑制ステップとを有することを特徴とするプログラム変換方法。
【請求項7】 請求項5の検出ステップ、変換ステップ、および削除ステップと、請求項6の変換抑制ステップとを有することを特徴とするプログラム変換方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、ソースコードを対象コードに変換するコンパイラ等に適用され、ループ処理中で用いられる誘導変数についてコードの最適化を行うプログラム変換装置、およびプログラム変換方法に関するものである。
【0002】
【従来の技術】コンパイラ等によってプログラムのソースコードを対象コードに変換する際などには、多くの場合、対象コードのサイズの低減や実行速度の向上等を目的として種々の最適化処理が行われ、そのうちのひとつとして誘導変数の最適化が行われることもある。
【0003】上記誘導変数は、例えば「コンパイラII」(A.Vエイホ R.セシィ J.D.ウルマン共著、原田賢一訳:サイエンス社)に記載されているように、ループ処理において、1回のループが繰り返されるごとに値が正又は負の一定量ずつ増加する変数のことで、その最適化とは、例えばソースコードにおいてループ処理の制御変数に所定の数を乗算して値を得る誘導変数が用いられている場合、前回のループ処理における誘導変数の値に上記所定の数を加算して新たな値を得るコードを生成することなどにより、処理速度の向上やコードサイズの低減を図ることである。
【0004】より具体的には、例えば図4(a)に示すコードにおいては、ラベルLからif文までの間のループ処理における変数a、bは1ループ処理ごとに値が2または6ずつ増加する誘導変数であるので、図4(b)に示すようなコードに変換することにより、2つの乗算を2つの処理時間の短い加算に置き換えることができる。
【0005】また、同様に図5(a)に示すコードにおいては、誘導変数c、d、eに関して図5(b)に示すようなコードに変換することにより、やはり乗算の数を減少させることができる。なお、コンパイラ等における上記のような誘導変数の最適化は、詳しくは、例えば以下のようにして行われる。
【0006】まず、ソースコードの構文解析等において、誘導変数を検出するとともに、その誘導変数のループごとの変化量を得る。次に、誘導変数を上記変化量(正又は負の値)だけ増加させてループごとの誘導変数の値を求めるコード、および誘導変数の初期値をセットするコード等を生成し、ソースコードを変換する。
【0007】ここで、従来のコンパイラ等においては、全ての誘導変数について、上記のような変換を行うようになっていた。
【0008】
【発明が解決しようとする課題】しかしながら、上記従来のコンパイラ等では、無駄な誘導変数の値を求めるコードが生成されたり、かえって処理速度の低下を招くようなコードが生成されたりすることがあるという問題点を有していた。すなわち、図4の例では、誘導変数a、b共について上記のような変換を行った結果、どこでも使用されない(厳密には、その誘導変数自身の新たな値を求めるため以外には使用されない)値を求める式a=a+2が生成されてしまう。このような誘導変数aに関する式a=0やa=a+2は不要であり、処理速度の低下やコードサイズの増大を招くことになる。
【0009】また、上記のような最適化が行われた誘導変数は、プロセッサのレジスタに割り付けられる優先順位が高い、いわゆるループ処理の中で生きる変数となる。それゆえ、図5の例のように常に全ての誘導変数について加算への変換を行うと、例えば誘導変数の数がプロセッサのレジスタ数を超える可能性が高くなり、その場合、レジスタの退避および復元のためのコードが増加し、かえってコードサイズの増大や処理速度の低下を招くことになりがちである。
【0010】本発明は上記の点に鑑み、無駄な誘導変数の値を求めるコードの生成を抑制したり、ループ処理の中で生きる変数の数を低減したりして、処理速度の向上やコードサイズの低減を図り得るプログラム変換方法、およびその装置の提供を目的としている。
【0011】
【課題を解決するための手段】上記目的を達成するため、本発明は、プログラムコードのループ処理中で用いられる誘導変数を検出する検出手段と、検出された誘導変数を示す情報を保持する保持手段と、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換手段と、検出手段で検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードを削除する削除手段とを有することを特徴としている。
【0012】また、プログラムコードのループ処理中で用いられる誘導変数を検出する検出手段と、検出された誘導変数を示す情報を保持する保持手段と、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換手段と、検出手段で検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換手段によるコードの変換を抑制する変換抑制手段とを有することを特徴としている。
【0013】また、プログラムコードのループ処理中で用いられる誘導変数を検出する検出ステップと、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換ステップと、検出ステップで検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードを削除する削除ステップとを有することを特徴としている。
【0014】また、プログラムコードのループ処理中で用いられる誘導変数を検出する検出ステップと、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する変換ステップと、検出ステップで検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換ステップの実行を抑制する変換抑制ステップとを有することを特徴としている。
【0015】
【作用】上記の構成により、検出手段は、プログラムコードのループ処理中で用いられる誘導変数を検出し、保持手段は、検出された誘導変数を示す情報を保持し、変換手段は、プログラムコードにおける、検出された誘導変数の値を定義するコードを、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換する。
【0016】さらに、削除手段が、検出手段で検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードを削除する。または、変換抑制手段が、検出手段で検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換手段によるコードの変換を抑制する。
【0017】また、検出ステップでは、プログラムコードのループ処理中で用いられる誘導変数が検出され、変換ステップでは、プログラムコードにおける、検出された誘導変数の値を定義するコードが、ループ処理が行われるごとに誘導変数に所定の値を加算することにより新たな誘導変数の値を定義するコードに変換される。さらに、削除ステップにより、検出ステップで検出された誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードが削除される。
【0018】または、変換抑制ステップにより、検出ステップで検出された複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、変換ステップの実行が抑制される。
【0019】
【実施例】以下、本発明の一実施例を図1ないし図3に基づいて説明する。図1はプログラム変換装置の構成を示すブロック図である。このプログラム変換装置による誘導変数の最適化は、例えばコンパイラに与えられるソースコードに対して行われるようにしてもよいし、また、コンパイラによるコンパイル処理の途中で得られる中間コードなどに対して行われるようにしてもよい。
【0020】図1において、最適化前コード記憶手段11は、上記ソースコードや中間コード等の最適化前コードを記憶するものである。誘導変数検出手段12は、最適化前コード記憶手段11に記憶されている最適化前コードに含まれる誘導変数を検出し、検出された誘導変数に関する情報を後述する誘導変数保持手段13に登録するものである。詳しくは、例えば最適化前コードにおけるループ処理中で誘導変数の値を定義する誘導変数定義文を検出し、誘導変数の変数名、1ループ処理ごとの増分値、および初期値を誘導変数保持手段13に保持させる。ここで増分値は、正の値でも負の値でもよい。なお、上記誘導変数の検出については、従来のプログラム変換装置と同様の構成が適用できるので、詳細な説明は省略する。
【0021】誘導変数保持手段13は、上記誘導変数検出手段12によって検出された誘導変数の変数名、1ループ処理ごとの増分値、および初期値を保持する。誘導変数最適化制御手段14は、定義文削除手段14aと、変換抑制手段14bとを備えて構成されている。定義文削除手段14aは、誘導変数保持手段13に登録された各誘導変数について、最適化前コードにおける、誘導変数(被使用誘導変数)の値が使用される使用文を検出し、検出された使用文が1つだけであり、かつ、その使用文で値を定義される変数が誘導変数保持手段13に登録されている場合、つまり被使用誘導変数を使用して定義される変数も誘導変数である場合に、被使用誘導変数の値を定義する定義文を最適化前コードから削除する。すなわち、上記被使用誘導変数の使用文は後述するコード変換処理によって被使用誘導変数を使用しない文に変換されるので、被使用誘導変数の定義文は不要なものとなり、したがってこれを削除することにより、コードサイズを低減するとともに処理速度を向上させることができる。定義文削除手段14aは、また、上記被使用誘導変数についてはコード変換処理を行う必要がないので、この被使用誘導変数についての登録を誘導変数保持手段13から削除する。
【0022】一方、変換抑制手段14bは、定義文削除手段14aと同様に被使用誘導変数の値が使用される使用文を検出した後、検出された使用文が複数あり、かつ、各使用文で値を定義される変数が全て誘導変数保持手段13に登録されている場合、つまりそれらの変数も誘導変数である場合に、それらの複数の誘導変数についての登録を誘導変数保持手段13から削除する。すなわち、削除された誘導変数については後述するコード変換処理が行われないので、プロセッサのレジスタに割り付けられる優先順位が高い、いわゆるループ処理の中で生きる誘導変数の数が少なく抑えられる。なお、上記各使用文で値を定義される変数が全て誘導変数保持手段13に登録されている場合に限らず、少なくとも複数の変数が登録されている場合などに、誘導変数保持手段13から削除するようにしてもよい。
【0023】コード変換手段15は、上記誘導変数最適化制御手段14の処理が完了した後、誘導変数保持手段13に登録されている誘導変数の変数名、1ループ処理ごとの増分値、および初期値に基づいて、最適化前コード記憶手段11に記憶されている最適化前コードにおける上記誘導変数の値を定義する定義文を、元の誘導変数の値に上記増分値を加算して新たな誘導変数の値を定義する定義文に変換するとともに、誘導変数の初期値をセットするコードを生成する。
【0024】最適化後コード記憶手段16は、コード変換手段15によって得られたコードを記憶する。上記の構成において、プログラム変換装置の動作を、図2(a)および図3(a)に示すコードに対して誘導変数の最適化が行われる場合を例に挙げて説明する。なお、以下の説明においては、簡単のためにループ処理の制御変数i、jに関する説明は省略する。
(例1)図2(a)に示すようなコードが最適化前コード記憶手段11に記憶されている場合、誘導変数検出手段12は、ラベルLからif文までの間のループ処理中で値を定義され、1ループ処理ごとに値が2または6ずつ増加する変数a、bを誘導変数として検出し、変数名「a、b」、1ループ処理ごとの増分値「2、6」、および初期値「0、0」を誘導変数保持手段13に登録する。
【0025】定義文削除手段14aは、誘導変数aの値が使用される使用文がb=a*3だけであり、さらに、この使用文で値を定義される変数bも誘導変数保持手段13に登録されていることを検出し、図2(b)に示すように、誘導変数aの値を定義する定義文a=2*iを最適化前コード記憶手段11に記憶されている最適化前コードから削除する。また、誘導変数保持手段13から誘導変数aについての登録を削除する。
【0026】コード変換手段15は、誘導変数保持手段13に登録されている変数名「b」、1ループ処理ごとの増分値「6」、および初期値「0」に基づいて、図2(c)に示すように、誘導変数bの値の定義文b=a*3をb=b+6に変換するとともに、誘導変数bの初期値をセットする文b=0を追加したコードを生成し、最適化後コード記憶手段16に記憶させる。ここで、上記誘導変数bの値の定義文b=b+6はラベルLからif文までの間のループ処理の後部(bの値を使用する関数f(b)よりも後)に配置され、初期値をセットする文b=0はラベルLよりも前に配置される。なお、このようなコードの変換に限らず、例えば誘導変数の初期値を−6とし、誘導変数bの値の定義文をループ処理の前部に配置するなど、アルゴリズムの等価な変換であればよい。
【0027】このようにして得られた最適化後コードは、ループ処理の制御変数iを除く誘導変数の定義文を1つだけ含み、しかもその誘導変数は加算によって値が求められるので、コードサイズが小さく抑えられるとともに、処理速度が向上される。
(例2)図3(a)に示すようなコードが最適化前コード記憶手段11に記憶されている場合、誘導変数検出手段12は、例1の場合と同様に、ラベルLからif文までの間のループ処理中で値を定義され、1ループ処理ごとに値が2、6、または8ずつ増加する変数c、d、eを誘導変数として検出し、変数名「c、d、e」、1ループ処理ごとの増分値「2、6、8」、および初期値「0、0、0」を誘導変数保持手段13に登録する。
【0028】変換抑制手段14bは、誘導変数cの値が使用される使用文がd=c*3、およびe=c*4の2つあり、さらに、これらの使用文で値を定義される変数d、eも共に誘導変数保持手段13に登録されていることを検出し、誘導変数保持手段13から誘導変数d、eについての登録を削除する。そこで、コード変換手段15は、誘導変数保持手段13に削除されずに登録されている変数名「c」、1ループ処理ごとの増分値「2」、および初期値「0」に基づいて、図3(b)に示すように、誘導変数cの値の定義文c=2*jをc=c+2に変換するとともに、誘導変数cの初期値をセットする文c=0を追加する一方、誘導変数d、eに関してはそのままで、最適化後コード記憶手段16に記憶させる。
【0029】このようにして得られた最適化後コードは、ループ処理の制御変数jを除けば、加算によって値が求められる誘導変数の定義文を1つだけ含むので、いわゆるループ処理の中で生きる変数の数が1つに抑えられ、プロセッサのレジスタに確実に割り付けられる可能性が高くなり、コードサイズが小さく抑えられるとともに、処理速度が向上される。
【0030】なお、上記の例では、定義文削除手段14aは、被使用誘導変数の値を定義する定義文を最適化前コード記憶手段11に記憶されている最適化前コードから削除する例を示したが、これに限らずコード変換手段15による変換が行われる際、または変換後のコードが最適化後コード記憶手段16に記憶された後に削除するようにしてもよい。
【0031】また、定義文削除手段14aは、最適化前コードにおける、誘導変数(被使用誘導変数)の値が使用される使用文を検出する例を示したが、これに限らず、例えばコード変換手段15による変換が行われた後のコードに対して使用文の検出をするようにしてもよい。この場合には、検出された使用文がその被使用誘導変数自身の新たな値を定義する文だけである場合に、その文を削除するようにすればよい。
【0032】また、プログラム変換装置の動作の説明では、定義文削除手段14a、または変換抑制手段14bの何れか一方だけによって誘導変数の登録の削除等が行われるような最適化前コードの例を示したが、一方の処理対象となった後に、さらに他方の処理対象となるようなコードの場合には、一層最適化されたコードが生成されることになる。
【0033】
【発明の効果】以上説明したように、本発明によれば、誘導変数が、1つの誘導変数の値を定義するためにのみ用いられる誘導変数である場合に、プログラムコードから、上記1つの誘導変数の値を定義するためにのみ用いられる誘導変数の値を定義するコードが削除され、または、複数の誘導変数が、同一の他の誘導変数を用いて値を定義される誘導変数である場合に、上記複数の誘導変数について、コードの変換が抑制されるので、無駄な誘導変数の値を求めるコードの生成が抑制され、または、ループ処理の中で生きる変数の数が低減され、したがって、処理速度の向上やコードサイズの低減が図られるという効果を奏する。




 

 


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

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


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