JPH03132828A - 共通の部分式を除去する方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はコンピュータ・プログラムのコンパイルに係り
、特に、コンピュータ・プログラムの最適化に関するも
のである。とりわけプログラム・ループの連続的な繰返
しにおける、共通部分式の削除の方法が詳細に述べられ
ている。

Ｂ、従来の技術 ］ンピュータ・プログラムが高級言語（例えばフォート
ラン、パスカル、コボル）で書かれた後、コンパイラ・
プログラムを用いて中間語命令シーケンスに変更される
。この中間語命令は、コンピュータで実行されるように
、順次機械語命令のシーケンス（目的言語）に変換され
る。高級言語で書かれたプログラムを中間コードで表現
するのに多くの方法がある。特に、機械語レベルに還元
されたある種の高級言語プログラムの中間語解釈は、他
の中間語解釈により生成された目的言語よりも短い時間
で実行される目的言語を生成する。そのため、コンパイ
ラ・システムはコードの最適化と呼ばれる処理手順を行
なうように構成されていることが多い。コードの最適化
は、プログラムの実行時間を減らすように中間コードを
改良する技術である。

Ｃ０発明が解決しようとする課題 ］−ドの最適化は多くの方法を経て達成される。

反復する計算は削除される。常に変らない変数は定数と
置換えてもよい。ループを展開することによって、ルー
プの複数回の繰返しに含まれていた連続した計算が、１
回の繰返しにおいて連続的に表われるようにすることが
できる。ループの繰返しにかかわらず同じ数値を求める
ループ内の数式はループの外に移してもよい。

コードの最適化の中でも特別の領域例えばプログラムの
反復部分が、プログラム・ループの走行時間を減らすの
に重要である。コンピュータ・プログラムはループ内の
命令を実行するために多くの時間を費やすので、ループ
の実行時間を減らすことのできるコード最適化の技法は
コンピュータ・プログラム全体の実行時間を減らすのに
特に有益である。

コードの最適化にとって重要な他の領域は、コンピュー
タ・プログラムから共通の部分式を除去することである
。共通の部分式はあるプログラム中で一回よりも多く発
生するコンピュータ動作であって、同じ計算結果の得ら
れるものである。コンピュータ・プログラムから共通の
部分式を除共することは最適化のために有効な技術であ
る。

０３課題を解決するための手段 本発明は、ループの連続した繰返しに共通の部分式を含
むコンピュータプログラムの最適化演算に関する。最適
化により、コンピュータプログラムはより短い時間で実
行される。

本発明は以下の一連のステップにより動作する。

最初のステップで、ループの１回の繰返しにおいて使用
されるシーケンス値が識別される。このシーケンスは、
そのシーケンスのメンバーの第１の部分集合の値が、ル
ープの次の繰返しにおいてシ−ケンスのメンバーの第２
の、非独占的な部分集合の値として用いられる。このシ
ーケンスが識別された時、中間プログラム・コードが修
正され、ループに入る前に、第２のサブセットのシーケ
ンス・メンバーの初期値が計算される。その後、各繰返
しにおいて、シーケンスの最初のサブセットの値だけが
計算される。第２のサブセットのメンバーに用いられる
値は、ループの先の繰返しの間に計算された値から得ら
れる。

本発明の他の特徴によれば、ループは展開され、それに
よって最も長いシーケンスの各メンバーのための、ルー
プの複写が１個存在する。次に、繰返しを通じて共通の
部分式の値を保持するために用いられる一時的な記憶位
置が、ループの複写の間、周期的に置換される。

Ｅ、実施例 まず、本発明の説明のために用いられる用語の定義を述
べる。

「共通の部分式、（ＣＯＭＭＯＮ　　５ＵＢ−ＥＸＰＲ
ＥＳＳ　Ｉ　ＯＮ） コンピュータ・プログラム中で何回も実行され同じ結果
を生ずる演算。例えば、式Ａ　：　＝Ｂ＋Ｃ＋ＤとＥ：
＝Ｂ＋Ｃ＋Ｆにおいて、Ｂ＋Ｃ（７）演算が共通の部分
式と呼ばれる。

「帰納変数Ｊ　　（ＩＮＤＵＣＴＩＯＮ　　ＶＡＲＩＡ
ＢＬＥ） ループＬの中だけで指定された変数■は、次のいずれか
の形式をとる。ｒ：＝ｒ＋ｃ又は■：＝Ｉ−に こでＣはループＬ内の定数。

例えば、表１を参照するに、変数Ｉはループ内で１から
１０まで計数するのに用いられている。

よって、変数Ｉは帰納変数と指称される。

「コードの移動Ｊ　　（ＣＯＤＥ　　ＭＯＴＩ　ＯＮ）
プログラムのループ内の命令の数を減らすことによりコ
ンピュータ・プログラムの走行時間を改善する方法。こ
れは、例えば、ループの各繰返しが同じ数値を求めるも
のであるとき、ループ内のコードを前にそのループで実
行された等価なコードに置変えるようなことを行なう。

ループ外のコードの数が増えても、全体の走行時間は減
少するかもしれない。

「アドレス指定順序Ｊ　　（ＡＤＤＲＥＳＳＩＮＧＳＥ
ＱＵＥＮＣＥ） 次のような特質を有する単一のアレーにアクセスするの
に用いられる記憶位置の値のセットａ）各記憶位置のア
ドレスがループの帰納変数に依存する。

ｂ）各記憶位置のアドレスが帰納変数の増分値だけその
前のもののアドレスと異なる。

［展開Ｊ　　（ＵＮＲＯＬＬ　ＩＮＧ）ループを書き直
すことにより、ループでなされる連続した計算が順次な
されるようにする方法。

例えば、 Ｄｏ　　Ｉ＝ＩＴＯ１００Ｂｙ　　Ｉ Ａ　（１）　＝Ａ　（１）　＋Ｂ　（Ｉ）ＥＮＤ　。

を２で展開すると次のようになる。

Ｄｏ　　Ｉ＝ＩＴＯ１００Ｂｙ　　２ Ａ　（１）　＝Ａ　（１）　十Ｂ　（１）　；Ａ　（１
＋１）＝Ａ　（１＋１）　十Ｂ　（１＋１）；ＥＮＤ ループの展開は、各繰返し毎にテストをして繰返し回数
を一定にするのを回避できる。よって、ループの展開は
実行される命令の数を減らすことができる。前の例では
、ループ制御のための増分とテストの数が半減される。

ループの展開では多くの命令が並列処理の対象になる。

前の例で、展開された形式における２つのステートメン
トは互に独立しているので同時に実行することができる
。

「再帰的な式Ｊ　　（ＲＥＣＵＲＲＥＮＣＥ　　ＥＸＰ
ＲＥＳＳ　Ｉ　ＯＮ） ループ内で見出される式であって、その値が先の繰返し
で計算された値に基いた一つの繰返しにより計算される
。

プログラムに再帰的な式を含むことは、ループの連続し
た繰返しにおける式の値を省（ために望ましいことであ
る。

表２は、再帰的な式を含むプログラムのためのソース・
コードを示している。ループの特定の繰返しにおけるＣ
ｌ３　（Ｊ）の値は、そのループの連続した繰返しにお
いてＣｌ３　（Ｊ−１）として用いられている。そのた
め、コンパイラ−にこの事実を認識させかつ連続したル
ープ繰返しの間−時レシスターにＣｌ３　（Ｊ）の値を
保持することが望ましい。

表２　再帰的な式を含むソース・コードの別表３と表４
は、表２に示されたプログラムの中間コードの解釈を示
している。表４に示された中間コードにおいて、再帰的
な式が認識され、そして、連続した繰返しのためにこの
再帰により生成された値を一時的に保管すべ（準備がな
される。

表３に示された解釈では、再帰は認識されていない。表
３では、Ｃｌ３　（Ｊ−１）がステップ１１０でＴｅｍ
ｐ　２にロードされる。このロード命令は、ループ（Ｌ
ＯＯＰ）の繰返し毎に実行される。表４でもまた、Ｃｌ
３　（Ｊ−１）の値がステップ１１０でＴｅｍｐ　２に
ロードされる。しかし、表４では、ループ（ＬＯＯＰ）
がステップ１２０で開始する。

これは、ＬＯＯＰの繰返し毎にＣｌ３　（Ｊ−１）をＴ
ｅｍｐ　２にロードすることを不要にする。

Ｃｌ３　（Ｊ）はステップ１５０でＴｅｍｐ　２に置か
れるので、ＬＯＯＰの連続した繰返しにおいて、Ｔｅｍ
ｐ　２はＣｌ３　（Ｊ−１）を含むとみなされる。

表４のＬＯＯＰは８個の命令からなり、他方表３のＬＯ
ＯＰは９個の命令からなるということを認識することは
重要である。これによって、再帰的な式によりループ繰
返し毎に１個の命令、あるいはプログラム全体を実行す
ることで７５０個の命令を節減できることがわかる。

真の再帰式に加えて、ループの一回の繰返しにおいて一
連の値がしばしば用いられ、シーケンスの他のメンバー
の値として次の繰返しにおいてシーケンスのいくつかの
メンバーが再び用いられる。

これらの値は、連続したループ繰返しの間共通の部分式
のセットを形成するものと考えてよい。そのようなシー
ケンスは繰返しを通じた共通の部分式削除（Ｃｒｏｓｓ
　Ｉｎｔｅｒａｔｉｏｎ　Ｃｏｍｍｏｎ　５ｕｂ−ｅｘ
ｐｒｅｓｓｉｏｎ　Ｅｌｉｍｉｎａｔｉｏｎ）により最
適化される。

この技術はまた、予測可能な共通化とも呼ばれる。例え
ば、一連の値の全メンバーが、最初の値を除いて次のル
ープの繰返しにおいて夫々異なるシーケンスのメンバー
として用いられるようなプログラム・ループを考えてみ
る。ループに入る前に、最初のメンバーを除いた全ての
シーケンスが計算される。その後、各繰返しはシーケン
スの最初のメンバーのみを計算しなければならない。ル
ープの最後に、全メンバーは、次の繰返しの間に見出さ
れるようにレジスターに移される。ループが展開され、
それにより最も長いシーケンスの各メンバーのためにル
ープ・コードの複写が存在する。

値のシーケンスを保持するのに用いられるレジスタのセ
ットを周期的に置換した後、メンバーを次の位置に移す
命令が削除される。

表５に、いくつかの再帰的な式を含むプログラムのソー
ス・コードが示されている。

このプログラムは、シーケンスＸ　（Ｊ＋ｌ、Ｋ）　、
Ｘ　（Ｊ、Ｋ）　、Ｘ　（Ｊ−１、Ｋ）を含んでいる（
ここでＫはｉ−１、ｉ及びｉ＋１の値をとる）。さらに
、和（１）はＪの和とＪ−１の和に対応するシーケンス
を形成する。

表６　中間コードの表示 表・６は、表５に示されたプログラムの中間コードの表
示を示している。この中間コードの表示は本発明の効果
を表わしている。

表６において、オリジナルのループは３つのコピーを形
成するように複写されている。メモリ位置のアドレスさ
れた第１セツト、第２のセットのデータは共に加えられ
、最初のループに入る前にＦＰ７と、ＦＰ５にロードさ
れる。これによって、プログラムはオリジナルの繰返し
単位において３つのロード操作（ｌｏａｄｓ　）と４つ
の加算操作（ａｄｄｓ）だけとなり、通常のプログラム
における９つのロード動作と８つの加算操作に比べて少
な（なる。

繰返しの間に実行される加算の結果は、次の繰返しにお
いて必要とされる全てのデータを繰り越すので、ロード
された量は保持されない。

浮動小数点レジスターＦＰ５、ＦＰ６及びＦＰ７は周期
的に入れ替えられ、内側ループの特別な繰返しによる計
算結果Ｘ　（Ｊ＋１、ｌ−１）十Ｘ（Ｊ＋１、Ｉ）＋Ｘ
　（Ｊ＋１、■＋１）を含んでいる。

この最適化を達成するのに用いられるアルゴリズムを記
述するのに、幾つかの用語を定義するのが有効である。

「（Ｘ）に依存するＪ　　（ｄｅｐｅｎｄｓ−ｏｎ　（
Ｘ）Ｌ・・・・・１つの入力としてＸを持つ式の推移的
閉包（ｔｒａｎｓｉｔｉｍｅ　ｃｌｏｓｕｒｅ）。

［無効Ｊ　（ｋｉｌｌ（ｖ））・・・・・・変数■に関
連する記憶値に依存する計算のセットが存在している場
合に、このセットのメンバーが■に関連して記憶位置を
変更するための命令により、無効にされると表現される
。無効の効果は、従来技術においては、共通部分式とし
ての変数の使用の終了である。

「否無効Ｊ　（ｄｏｎｔ−ｋｉｌｌ　（ｘ、　　１））
−−（Ｘ）に依存するシーケンスのメンバーのサブセッ
トＸが、特別なループ内の特別な無効命令、ｉによって
は影響されないことが知られている。

「否無効Ｊ　（ｄｏｎｔ−ｋｉｌｌ　（ｒ））命令は次
のとおり。

ｄｏｎｔ　ｋｉｌｌ（ｒ）　＝ ｑｓｓ、ｑ≠ｒ ここで、Ｓはシーケンス、ｑｓは否無効シーケンス・メ
ンバー　ｒは無効命令により影響されるシーケンス・メ
ンバーである。

［（Ｘ）に続けてもよいＪ　（ｍａｙ−ｆｏｌｌｏｗ（
Ｘ））−・・・どれかの計算（Ｘ）のための計算のセッ
トであり、コンピュータ・プログラム内のシーケンスで
シーケンスのＸに依存するメンバーが各々後続のメンバ
ーにより置変えられる。

もし、Ｘがシーケンス・メンバーやシーケンスメンバー
により構成される量や不変量よりも、ループの変化量に
依存するならば、「（Ｘ）に続く」は空文字にするよう
定義される。

「利用可能な」（ａｖａｉｌａｂｌｅ）・・・・・・プ
ログラムの特別の点において、前に完了し、削除されて
いない操作のセット。

「リインカーネイトＪ　（ｒｅｉｎｃａｒｎａｔｅ）・
・・・・・ある繰返しにおいて使用され、続く繰返しに
おいて再利用可能な計算のセット。

ｒｅｉｎｃａｒｎａｔｅ＝ 本発明の動作は第１図に要約されている。

ステップ１００で、ソース・プログラムは本発明に適合
する中間コード表現を生成するようにコンパイルされる
。この表現は、コンピュータの主記憶装置のアレイ要素
にアクセスするのに用いられるアドレス計算の識別を可
能にする。（例えば、ロード命令はベースとインデック
スレジスターを用いる）。この表現は、それらにアドレ
ス計算が依存するループの帰納変数の決定をも可能にす
る。

ステップ２００で、各帰納変数に対する記憶参照のパタ
ーンが分析される。これは、プログラムの内側ループの
全てのメモリ動作（例えばロードやストア）を調べるこ
とによってなされる。

特に、同じ帰納変数に基いて、かつある特定の増分だけ
異なる２つのメモリ・アクセスに対して調査がなされる
。これらのメモリ・アクセスは、長さ２のアドレス・シ
ーケンスを形成すると言える。全ての長さ２のアドレス
・シーケンスが探し出され、もし可能ならば、より長い
シーケンスを形成するようにつなぎ合わされる。

ステップ３００で、修正されたコードの移動と共通の部
分式の削除がなされる。参考技術が、工イホ等（Ａｈｏ
　ｅｔ　ａｌ、）著、「コンパイラ・デザインの原理」
（Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｃｏｍｐｉｌｅｒ　Ｄ
ｅｓｉｇｎ）、アデイソン・ウニスレー（八ｄｄｉｓｏ
ｎ　Ｗｅｓｌｅｙ）、１９７９年刊の４５４〜４６６真
に示されている。

コードの移動の最適化のために、一般に知られた技術を
用いることができる。また、よく知られた共通の部分式
の削除の方法を用いることもできる。

本発明の最適な実施のために、コックとシュバルツのア
ルゴリズム（Ｃｏｃｋｅ　ａｎｄ　Ｓｃｈｗａｒｔｚａ
ｌｇｏｒｉ　ｔｈｍ）を用いている。

コック（Ｃｏｃｋｅ、Ｊ、　）著「包括的な共通の部分
式０式％ ニア １９７０年刊の２０頁〜２４頁を参照のこと。

共通の部分式の削除は、典形的には、単一のループから
共通の部分式の１つの数値を求めることを除いて全てを
削除するものである。削除された数値は局地的に記憶さ
れた値を参照することによって置変えられる。この値は
、保持された１つの共通の部分式の数値を示す。そのよ
うな値は、例えば、−時的なレジスターにストアするこ
とができる。

本発明の目的のために、共通の部分式の削除は、連続し
たループの繰返しの間に共通の部分式を最適化するよう
に修正される。これは、現在のループの繰返しにおいて
アクセスされた値を、−時的に後のループ繰返しのため
に保持することを可能にする。これによって、メモリ・
アクセス及び計算ステップの繰返しが回避される。

本発明の実施例では、ステップ２００に示すように、デ
ータ値が再帰的な式のシーケンスによりアドレスされた
アレーにストアされている。

通常の共通の部分式の削除では、各発生セグメントが取
出されるアレー値のインデックスが生じる読取り動作の
数を減らすために、各ループの繰返しの間にこのアレー
の量は一時的レジスタに割り当てられる。

これらのアルゴリズムによって、ループの繰返しの間共
通するアレーからの量は、通常、各繰返しの終りに無効
にされ、その次の繰返しで必要なときは計算されなけれ
ばならない。実施例によれば、無効にする動作は行なわ
れない。

第２図は第１図のステップ３００の詳細を示すものであ
る。第２図において、ステップ３１０で先に与えられた
定義に従って、各メモリ書込み動作に対して「否無効」
セットの決定がなされる。

各再帰的な式は「否無効ｊセットのメンバーである。そ
のため、これらの表現がされたレジスターの記憶は無効
にされない。次に、ステップ３２０で、各シーケンスに
ついてセットの「リインカーネイト」　（生れ変り）が
計算される。このセットは、あるループの繰返しにおい
て否無効の値を次のループの繰返しにおける対応する値
と関係づける。

ステップ３３０で、プログラム内の各シーケンスに関連
する帰納変数の増分の位置が突きとめられる。

ステップ３４０で、修正された共通化及びコードの移動
動作が実行される。これらの動作は、「リインカーネイ
ト」セットの全メンバーがステップ３３０で確立された
プログラム内の位置で計算されるかのようにふるまう。

これらの値を異なるレジスターに移す指令は付加されて
いないので、ループ・コードを展開し、再帰的な式の値
を保持するのに用いられているレジスタを置換するのが
望ましい。（第１図、ステップ４００）。

第１図のステップ４００でループは展開され、オリジナ
ル・ボディーを複写した数値は見出された再帰的な式の
最も長いメンバーの数値と等しい。

ループの展開において、ループを展開するにはどんな方
法を用いてもよい。実施例の方法としては、前記エイホ
等の著「コンパイラ・デザインの原理」の４７１〜４７
３頁を参照する。

ループが展開されると、各シーケンスの計算の名称（例
えば個々の計算に密接に関係するレジスタ）が置換され
る。これは、計算結果（例えば特別のアレー・エレメン
トの値）を１回の繰返しにおいて１つのレジスタ内に置
き、次の繰返しにおいて別の計算（例えば、次の繰返し
の間、コードの別の部分に用いる、同じアレー・エレメ
ントの値）のために用いることができる。このタイプの
置換を用いることにより、１つのループ繰返しから次へ
再帰的な式の値を複写するステップを削除できる。

もし、ループが複数のループに展開され、その数がオリ
ジナルの繰返し回数の積分値でないとき、残りのループ
が残りの繰返しを達成するように作り出される。この残
りのループに、後に続くループの繰返しのために、「リ
インカーネイト」セットを別の一時的なレジスタに複写
するように、指令が付加される。

Ｆ、効果 本発明によればコンピュータ・プログラムのループの繰
返しに共通の部分式を含むとき、この共通の部分式を削
除するようにコンピュータ・プログラムが修正されるた
め、ループ繰返し命令を節減し、もってループの走行時
間を減少させることができる。

【図面の簡単な説明】

第１図は本発明の実施例の動作を説明するためのフロー
チャートであり、第２図は第１図のステップ３００の詳
細を示すフローチャートである。 １００・・・・・・中間コードの生成 ２００・・・・・・連続したループ繰返し内の共通の部
分式の識別 ３００・・・・・・修正された共通の部分式の削除とコ
ード移動の実行 ４００・・・・・・ループの展開

Claims (8)

【特許請求の範囲】
1. （１）、コンピュータ・プログラムのループの繰返しに
   おける共通の部分式を除去するための方法であつて、そ
   の共通の部分式は帰納変数に依存するものにおいて、 ａ）上記共通の部分式を識別するステップと、 ｂ）上記ループの繰返しにおける共通の部分式の数値を
   保持するよう、上記コンピュータ・プログラムを修正す
   るステップと、 ｃ）上記ループの繰返しにおいて、共通の部分式に上記
   保持された数値を用いるように上記プログラムを修正す
   るステップ、 とを含むことを特徴とする共通の部分式を除去する方法
   。
2. （２）、請求項（１）において、 上記ステップｂ）は、上記共通の部分式に対して、否無
   効セットを定義するステップを含み、該否無効セットは
   、共通の帰納変数を持つ複数のアドレス計算を含み、 該セットにおいて上記アドレス計算は無効命令によつて
   影響されない、 ことを特徴とする共通の部分式を除去する方法。
3. （３）、請求項（１）において、 上記ステップｃ）は上記帰納変数が増分された後のある
   点において上記共通の部分式のために上記セットをリイ
   ンカーネイトすることを決定するステップを含む、 ことを特徴とする共通の部分を除去する方法。
4. （４）、請求項（３）において、 共通の部分式のセットが識別され、該セット内の共通の
   部分式が共通の帰納変数に依存し、１つのアレーの別々
   の記憶位置に夫々対応し、該位置は上記帰納変数によつ
   て定義された増分毎に分離されており、さらに、 ｄ）上記共通の部分式のメンバーの数に等しい数のルー
   プの複写を生成するために上記ループを展開するステッ
   プ、 を含むことを特徴とする共通の部分式を除去する方法。
5. （５）、請求項（４）において、上記ステップｄ）は、
   上記ループが展開されたとして計算を入れ換えるステッ
   プを含むことを特徴とする共通の部分式を除去する方法
   。
6. （６）、請求項（１）において、上記ステップａ）に先
   行して、上記プログラムをステップａ）の識別動作を容
   易にする書式に変換するステップを含むことを特徴とす
   る共通の部分式を除去する方法。
7. （７）、ループの連続した繰返しから冗長な計算を除去
   する方法であつて、 ａ）冗長な計算を識別するステップと、 ｂ）上記計算を削除するステップと、 ｃ）上記計算を実行しその結果を次の繰返しでアクセス
   される位置に保持するステップ、を含むことを特徴とす
   る、冗長な計算を除去する方法。
8. （８）、請求項（７）において、 上記ステップａ）に先行して、コードの移動を行なうス
   テップを含むことを特徴とする、冗長な計算を除去する
   方法。