JPH03150636A - コンパイル方法 - Google Patents
コンパイル方法Info
- Publication number
- JPH03150636A JPH03150636A JP1290188A JP29018889A JPH03150636A JP H03150636 A JPH03150636 A JP H03150636A JP 1290188 A JP1290188 A JP 1290188A JP 29018889 A JP29018889 A JP 29018889A JP H03150636 A JPH03150636 A JP H03150636A
- Authority
- JP
- Japan
- Prior art keywords
- loop
- procedure
- array data
- register
- index
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
- G06F8/451—Code distribution
- G06F8/452—Loops
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明（友 配列データを扱う演算を含んだループ文に
対するコンパイル方法に関すも 従来の技術 従来のコンパイル方法をプログラム例を用いて説明すも 第１７図はプログラム例１のＦＯＲＴＲＡＮコード医
第１８図はプログラム例２０ＦＯＲＴＲＡＮコード医
第１９図はプログラム例１に対する疑似オブジェクトコ
ード阻 第２０図はプログラム例２に対する疑似オブジ
ェクトコード図であも また 疑似オブジェクトコード
（以下、疑似コードと呼ぶ）において、各コードは次の
動作を表も ［ループの初期設定］ Ｌ ＯＯＰ Ｅ Ｎ Ｔ ＲＹ ｘ ＝ ｙ、
ｚ、 ｗインデックスはＸて 初期値がｙス 最終値
が２玄 増分値がＷであａ ［レジスタへのロード］ ＬＯＡＤ ＃ｘ、 ｒｅｇｙ メモリＸの内容を、 レジスタｙヘロードすａ［加算〕 ＡＤＤ ｒｅｇｘ、 ｒｅｇｙ＋ ｒｅｇｚＡ
Ｄ Ｄ ｒ ｅ ｇ ｘ、 ＃ ５’ｔ ｒ ｅ
ｇ ｚｒｅｇｚ＝ｒｅｇｘ十ｒｅｇｙ ｒｅｇｚ＝ｒｅｇｘ＋＃ｙ ［レジスタからのストア］ ５ＴＯＲＥ ｒｅｇｘ、 ＃ｙ メモリｙヘレジスタＸをストアすも ［レジスタ間のムーブ］ ＭＯＶＥ ｒｅｇｘ、 ｒｅｇｙ レジスタＸをレジスタｙヘコビーすム ［ループの後処理］ Ｌ ＯＯＰ ＲＥ Ｔ Ｕ ＲＮ ｘ ＝ ｘ 十
ｙ、 ｚＸにｙを加Ｌｚへ飛本 終了判定が真になれ
ば ループを抜けも ま哄 第１７図の例であるが（プログラム例１）、これ
を従来の方法でコンパイルすると第１９図のようになも
つまり、最初番ζ ループの初期設定を行なう。つぎ
く ループボディの最初−′Ｃ５Ｂ（Ｉ−１）およびＢ
（Ｉ）をロードし それらを加算し さらにＢ （Ｉ
＋１＞をロードしてそれも加算すも 最後く その結果
をＡ （Ｉ）にストアしてループリターンを書く。
対するコンパイル方法に関すも 従来の技術 従来のコンパイル方法をプログラム例を用いて説明すも 第１７図はプログラム例１のＦＯＲＴＲＡＮコード医
第１８図はプログラム例２０ＦＯＲＴＲＡＮコード医
第１９図はプログラム例１に対する疑似オブジェクトコ
ード阻 第２０図はプログラム例２に対する疑似オブジ
ェクトコード図であも また 疑似オブジェクトコード
（以下、疑似コードと呼ぶ）において、各コードは次の
動作を表も ［ループの初期設定］ Ｌ ＯＯＰ Ｅ Ｎ Ｔ ＲＹ ｘ ＝ ｙ、
ｚ、 ｗインデックスはＸて 初期値がｙス 最終値
が２玄 増分値がＷであａ ［レジスタへのロード］ ＬＯＡＤ ＃ｘ、 ｒｅｇｙ メモリＸの内容を、 レジスタｙヘロードすａ［加算〕 ＡＤＤ ｒｅｇｘ、 ｒｅｇｙ＋ ｒｅｇｚＡ
Ｄ Ｄ ｒ ｅ ｇ ｘ、 ＃ ５’ｔ ｒ ｅ
ｇ ｚｒｅｇｚ＝ｒｅｇｘ十ｒｅｇｙ ｒｅｇｚ＝ｒｅｇｘ＋＃ｙ ［レジスタからのストア］ ５ＴＯＲＥ ｒｅｇｘ、 ＃ｙ メモリｙヘレジスタＸをストアすも ［レジスタ間のムーブ］ ＭＯＶＥ ｒｅｇｘ、 ｒｅｇｙ レジスタＸをレジスタｙヘコビーすム ［ループの後処理］ Ｌ ＯＯＰ ＲＥ Ｔ Ｕ ＲＮ ｘ ＝ ｘ 十
ｙ、 ｚＸにｙを加Ｌｚへ飛本 終了判定が真になれ
ば ループを抜けも ま哄 第１７図の例であるが（プログラム例１）、これ
を従来の方法でコンパイルすると第１９図のようになも
つまり、最初番ζ ループの初期設定を行なう。つぎ
く ループボディの最初−′Ｃ５Ｂ（Ｉ−１）およびＢ
（Ｉ）をロードし それらを加算し さらにＢ （Ｉ
＋１＞をロードしてそれも加算すも 最後く その結果
をＡ （Ｉ）にストアしてループリターンを書く。
次く 第１８図の例であるが（プログラム例２）、これ
を従来の方法でコンパイルすると第２０図のようになム
つまり、最初へ ループの初期設定を行なう。つぎく
ループボディの最初で、Ａ（Ｉ−１’）をロードし
それと即値ｌを加算しその結果をＡ （Ｉ）にストアし
ざらにＡ （Ｉ＋１）をロードしてそれと即値２も加
算すも 最後く その結果をＡ （Ｉ−１）にストアし
てループリターンを書く。
を従来の方法でコンパイルすると第２０図のようになム
つまり、最初へ ループの初期設定を行なう。つぎく
ループボディの最初で、Ａ（Ｉ−１’）をロードし
それと即値ｌを加算しその結果をＡ （Ｉ）にストアし
ざらにＡ （Ｉ＋１）をロードしてそれと即値２も加
算すも 最後く その結果をＡ （Ｉ−１）にストアし
てループリターンを書く。
以上のようへ 従来の方法で（よ 同じデータを異なっ
たインデックス値の時に複数回ロード及びストアしてい
も 例えば プログラム例１の疑似コードにおいて（上
Ｂ（３）の値４−ＬＩ＝２の時のＢ （Ｉ＋１）、及
びＩ＝３の時のＢ （Ｉ）、及びＩ＝４（７）時ノＢ
（Ｉ−１） テｏ−ドしｒ い＆また プログラム例２
の疑似コードにおいて（友Ａ（３）の値を、 Ｉ＝３の
時のＡ （Ｉ）、及びＩ＝４の時のＡ （Ｉ−１）でス
トアＬＡ Ｉ＝４の時のＡ （Ｉ−１）、及びＩ＝２の
時のＡ （Ｉ＋１）でロードしていも 発明が解決しようとする課題 従来のコンパイル方法で１上 メモリへのアクセスが必
要以上に生じも 本発明（よ かかる問題点に鑑へ 配列名が同じでイン
デックスの異なる配列データに対応するレジスタの内容
をループリターンの前にループの進む順にムーブさせ、
またストアするもののうち最小のものだけストアするこ
とにより、ロード／ストアの回数を縮小でき、さらく
ループをアンロールすることにより、レジスタのムーブ
を省略できるコンパイラ方法を提供することにあ４課題
を解決するための手段 本発明線 前記課題を解決するためへ 配列データを扱
う演算を含んだループ文のプログラムのコンパイルにお
いて、プログラム中の配列データの検出手続きと、ルー
プ箇所の検出手続きとを含み、 前記ループ文のコンパ
イル結果をループにはいる前の前処理部分であるループ
エントリと繰り返す演算部分であるループボディとルー
プを繰り返すための後処理部分であるループリターンの
３つの部分から成るとする隊 前記配列データのうち異
なった配列名及び異なったインデックスを持つものをそ
れぞれ別のレジスタに割り当てる手続きと、前記配列デ
ータのうちインデックスが最大のもの以外のものに対応
する前記レジスタへのメモリからロードをループエント
リの前で行なう手続きと、前記配列データのうちインデ
ックスが最大のものに対応する前記レジスタへのメモリ
からロードをループボディの中で行なう手続きと、ルー
プボディの中で前記配列データに対応する前記レジスタ
の内容をその配列データのインデックスと異なる前記配
列データに対応する前記レジスタにムーブする手続きと
、前記配列データのメモリへのストアが必要な時はルー
プボディの中で少なくともインデックスの最小なものを
メモリヘスドアする手続きと、それ以外をループリター
ンの後でストアする手続きとを含むことを特徴とするコ
ンパイル方法であも また本発明は上記構成において、前記レジスタヘムーブ
する手続きを行なわずに、 前記配列データのインデッ
クスのループ内での最大差異値の整数倍回だけループを
アンロールする手続きを含むことを特徴とするコンパイ
ル方法であ４作用 本発明（友 上記構成のレジスタの割当方法を適用して
レジスタ割当方法を変えることにより、配列データの演
算を含むループ文の実行を無駄なメモリのアクセスをな
くした分、高速実行させることができも また アンロ
ーリング手法によりレジスタのムーブを省略できも 実施例 本実施例を従来例の説明と同じく、プログラム例１ （
第１７図）及びプログラム例２（第１８図）を用いて説
明すも 第１図は本発明の第１のコンパイル方法のフローｔｎ
第２図は本発明の第２のコンパイル方法のフロー医
第３〜７図（よ プログラム例１に対して第１のコンパ
イル方法を適用した場合の説明医第８図はプログラム例
１の第１のコンパイル方法によるコンパイル結果のコー
ドは 第９図はプログラム例２の第１のコンパイル方法
によるコンパイル結果のコード図 第１０〜１４図はプ
ログラム例１に対して第２のコンパイル方法を適用した
場合の説明諷 第１５図はプログラム例１の第２のコン
パイル方法によるコンパイル結果のコード図 第１６図
はプログラム例２の第２のコンパイル方法によるコンパ
イル結果のコード図であも第１のコンパイル方法（よ
第１図に示すように７つの手続きから構成され翫 ま哄
ループ箇所検出手続き１’Ｑ ソースプログラムの
中でループ構造になっている部分を検出し 続く配列デ
ータ検出手続き２て そのループ構造の中で参照してい
る配列データを検出すも これらの配列データのうちで
異なった配列名及び異なったインデックスを持つものを
それぞれ別のレジスタに割り当てるレジスタ割り当て手
続き３を経た抵 ロード命令移動手続き４玄 インデッ
クスの範囲を求へインデックスの最大のもの以外をルー
プの前でロードす翫 次１ ロード命令生成手続き５て
インデックスの最大のものをループボディの中でロー
ド命令を生成すａ さらへ ストア命令生成手続き６て
インデックスの最小のものに対するストア命令のみを
ループボディの中で生成すも それ以外はループリター
ンの後でストア命令を生成すも 最後へ レジスタ間移
動手続き７で異なったインデックスを持つもののレジス
タの内容を他のレジスタヘムーブすも 一人 第２項のコンパイル方法Ｌ 第２図に示すよう
に７つの手続きから構成されも ま哄 ループ箇所検出
手続き１、及び配列データ検出手続き２は第１のコンパ
イル方法と同様であも 続く、ループアンローリング手
続き８１ヨ ループ内で用いられているインデックス
の範囲を求へ その整数倍だけループを展開するもので
あム 残りの手続き３〜６（よ 第１のコンパイル方法
と同様であこれらの第１，２のコンパイル方法の手続き
に添って、プログラム例を処理していく。ま哄 プログ
ラム例１を第１のコンパイル方法でコンパイルすも ル
ープ箇所検出手続き１、及び続く配列デ−タ検出手続き
２て ループ箇所及びその中で参照している配列データ
（Ｂ （Ｉ＋１）、Ｂ （Ｉ）。
たインデックス値の時に複数回ロード及びストアしてい
も 例えば プログラム例１の疑似コードにおいて（上
Ｂ（３）の値４−ＬＩ＝２の時のＢ （Ｉ＋１）、及
びＩ＝３の時のＢ （Ｉ）、及びＩ＝４（７）時ノＢ
（Ｉ−１） テｏ−ドしｒ い＆また プログラム例２
の疑似コードにおいて（友Ａ（３）の値を、 Ｉ＝３の
時のＡ （Ｉ）、及びＩ＝４の時のＡ （Ｉ−１）でス
トアＬＡ Ｉ＝４の時のＡ （Ｉ−１）、及びＩ＝２の
時のＡ （Ｉ＋１）でロードしていも 発明が解決しようとする課題 従来のコンパイル方法で１上 メモリへのアクセスが必
要以上に生じも 本発明（よ かかる問題点に鑑へ 配列名が同じでイン
デックスの異なる配列データに対応するレジスタの内容
をループリターンの前にループの進む順にムーブさせ、
またストアするもののうち最小のものだけストアするこ
とにより、ロード／ストアの回数を縮小でき、さらく
ループをアンロールすることにより、レジスタのムーブ
を省略できるコンパイラ方法を提供することにあ４課題
を解決するための手段 本発明線 前記課題を解決するためへ 配列データを扱
う演算を含んだループ文のプログラムのコンパイルにお
いて、プログラム中の配列データの検出手続きと、ルー
プ箇所の検出手続きとを含み、 前記ループ文のコンパ
イル結果をループにはいる前の前処理部分であるループ
エントリと繰り返す演算部分であるループボディとルー
プを繰り返すための後処理部分であるループリターンの
３つの部分から成るとする隊 前記配列データのうち異
なった配列名及び異なったインデックスを持つものをそ
れぞれ別のレジスタに割り当てる手続きと、前記配列デ
ータのうちインデックスが最大のもの以外のものに対応
する前記レジスタへのメモリからロードをループエント
リの前で行なう手続きと、前記配列データのうちインデ
ックスが最大のものに対応する前記レジスタへのメモリ
からロードをループボディの中で行なう手続きと、ルー
プボディの中で前記配列データに対応する前記レジスタ
の内容をその配列データのインデックスと異なる前記配
列データに対応する前記レジスタにムーブする手続きと
、前記配列データのメモリへのストアが必要な時はルー
プボディの中で少なくともインデックスの最小なものを
メモリヘスドアする手続きと、それ以外をループリター
ンの後でストアする手続きとを含むことを特徴とするコ
ンパイル方法であも また本発明は上記構成において、前記レジスタヘムーブ
する手続きを行なわずに、 前記配列データのインデッ
クスのループ内での最大差異値の整数倍回だけループを
アンロールする手続きを含むことを特徴とするコンパイ
ル方法であ４作用 本発明（友 上記構成のレジスタの割当方法を適用して
レジスタ割当方法を変えることにより、配列データの演
算を含むループ文の実行を無駄なメモリのアクセスをな
くした分、高速実行させることができも また アンロ
ーリング手法によりレジスタのムーブを省略できも 実施例 本実施例を従来例の説明と同じく、プログラム例１ （
第１７図）及びプログラム例２（第１８図）を用いて説
明すも 第１図は本発明の第１のコンパイル方法のフローｔｎ
第２図は本発明の第２のコンパイル方法のフロー医
第３〜７図（よ プログラム例１に対して第１のコンパ
イル方法を適用した場合の説明医第８図はプログラム例
１の第１のコンパイル方法によるコンパイル結果のコー
ドは 第９図はプログラム例２の第１のコンパイル方法
によるコンパイル結果のコード図 第１０〜１４図はプ
ログラム例１に対して第２のコンパイル方法を適用した
場合の説明諷 第１５図はプログラム例１の第２のコン
パイル方法によるコンパイル結果のコード図 第１６図
はプログラム例２の第２のコンパイル方法によるコンパ
イル結果のコード図であも第１のコンパイル方法（よ
第１図に示すように７つの手続きから構成され翫 ま哄
ループ箇所検出手続き１’Ｑ ソースプログラムの
中でループ構造になっている部分を検出し 続く配列デ
ータ検出手続き２て そのループ構造の中で参照してい
る配列データを検出すも これらの配列データのうちで
異なった配列名及び異なったインデックスを持つものを
それぞれ別のレジスタに割り当てるレジスタ割り当て手
続き３を経た抵 ロード命令移動手続き４玄 インデッ
クスの範囲を求へインデックスの最大のもの以外をルー
プの前でロードす翫 次１ ロード命令生成手続き５て
インデックスの最大のものをループボディの中でロー
ド命令を生成すａ さらへ ストア命令生成手続き６て
インデックスの最小のものに対するストア命令のみを
ループボディの中で生成すも それ以外はループリター
ンの後でストア命令を生成すも 最後へ レジスタ間移
動手続き７で異なったインデックスを持つもののレジス
タの内容を他のレジスタヘムーブすも 一人 第２項のコンパイル方法Ｌ 第２図に示すよう
に７つの手続きから構成されも ま哄 ループ箇所検出
手続き１、及び配列データ検出手続き２は第１のコンパ
イル方法と同様であも 続く、ループアンローリング手
続き８１ヨ ループ内で用いられているインデックス
の範囲を求へ その整数倍だけループを展開するもので
あム 残りの手続き３〜６（よ 第１のコンパイル方法
と同様であこれらの第１，２のコンパイル方法の手続き
に添って、プログラム例を処理していく。ま哄 プログ
ラム例１を第１のコンパイル方法でコンパイルすも ル
ープ箇所検出手続き１、及び続く配列デ−タ検出手続き
２て ループ箇所及びその中で参照している配列データ
（Ｂ （Ｉ＋１）、Ｂ （Ｉ）。
Ｂ（Ｉ−１）、Ａ（Ｉ））を検出できも レジスタ割り
当て手続き３で、これらのデータにレジスタを割り当て
ると、第３図のようになａ さらにこれらのレジスタを
用いて、疑似コードを作ると第４図のようになａ 次＆
へ ロード命令移動手続き４℃ インデックスの範囲を
求めると、 Ｉ−１〜Ｉ＋１なの六 Ｂ （Ｉ−１）、
Ｂ （Ｉ）をループの前でロードして疑似コードを作る
と、第５図のようになも ロード命令生成手続き５’ｒ
、Ｂ（Ｉ＋１）に対するロード命令を生成し 疑似コー
ドを作ると、第６図のようになａ 続いて、ストア命令
生成手続き６で、Ａ （Ｉ）に対するストア命令をルー
プボディの中で生成し 疑似コードを作ると、第７図の
ようになへ 最後番ζ レジスタ間移動手続き７を行な
うと第８図のようになａこのようく このプログラム例
１に対してＧＥＬループ内のロードが３回から１回に減
らせた次く プログラム例２に対してだ爪 大力はプロ
グラム例１と同様に行なう。しかし ループ内″ｕＡに
対して２回ストアしているので、ストア命令生成手続き
６でインデックスの小さいものに対するストア命令だけ
をループ内で生成すん この疑似ツー下を、第９図に示
も 次へ 前記プログラム例Ｉを第２のコンパイル方法でコ
ンパイルする場合を考えも この例でのインデックスの
範囲はＩ−１〜Ｉ＋１なの六 この場合ループアンロー
リング手続き８でループを３倍に展開しく第１１図）、
レジスタ割り当て手続き３で配列データに対して、レジ
スタを割り当てる（第１０図）。この隊 Ｂ （Ｉ−１
）とＢ（Ｉ＋２）及びＢ （Ｉ）とＢ （Ｉ＋３）及び
Ａ（Ｉ）とＡ （Ｉ＋１）とＡ （Ｉ＋２）がレジスタ
を共有していも このレジスタを使った疑似コードを第
１２図に水塊 さらへ ロード命令移動手続き４を行な
い（第１３図）、ロード命令生成手続き５を行なう（第
１４図）。最後へ ストア命令生成手続き６を行な（＼
この結果を示したのが第１５図であも このようＪｌ−、ループをアンロールすることにより、
ループリターン時には次のループボディの最初で用いる
レジスタがセットされているの玄 レジスタ間のコピー
が不用となも つまり、プログラム例１の場合を見ると
、 Ｉ＝３の時のループボディの最後で（戴 ｒｅｇｏ
にＢ（５）がセットさり、ｒｅｇｌにＢ（６）がセット
さり、ｒｅｇ３にＢ（４）がセットされ 次のＩ＝６の
ループボディの最初で必要となるレジスタセット（ｒｅ
ｇＯ＝Ｂ （５）、 ｒｅｇｌ＝Ｂ （６）、 ｒｅｇ
３＝Ｂ （７） ）が達成されていも 最後１−、 プログラム例２に対しても同様に行なう
ことができ、この結果を、第１６図に示す。
当て手続き３で、これらのデータにレジスタを割り当て
ると、第３図のようになａ さらにこれらのレジスタを
用いて、疑似コードを作ると第４図のようになａ 次＆
へ ロード命令移動手続き４℃ インデックスの範囲を
求めると、 Ｉ−１〜Ｉ＋１なの六 Ｂ （Ｉ−１）、
Ｂ （Ｉ）をループの前でロードして疑似コードを作る
と、第５図のようになも ロード命令生成手続き５’ｒ
、Ｂ（Ｉ＋１）に対するロード命令を生成し 疑似コー
ドを作ると、第６図のようになａ 続いて、ストア命令
生成手続き６で、Ａ （Ｉ）に対するストア命令をルー
プボディの中で生成し 疑似コードを作ると、第７図の
ようになへ 最後番ζ レジスタ間移動手続き７を行な
うと第８図のようになａこのようく このプログラム例
１に対してＧＥＬループ内のロードが３回から１回に減
らせた次く プログラム例２に対してだ爪 大力はプロ
グラム例１と同様に行なう。しかし ループ内″ｕＡに
対して２回ストアしているので、ストア命令生成手続き
６でインデックスの小さいものに対するストア命令だけ
をループ内で生成すん この疑似ツー下を、第９図に示
も 次へ 前記プログラム例Ｉを第２のコンパイル方法でコ
ンパイルする場合を考えも この例でのインデックスの
範囲はＩ−１〜Ｉ＋１なの六 この場合ループアンロー
リング手続き８でループを３倍に展開しく第１１図）、
レジスタ割り当て手続き３で配列データに対して、レジ
スタを割り当てる（第１０図）。この隊 Ｂ （Ｉ−１
）とＢ（Ｉ＋２）及びＢ （Ｉ）とＢ （Ｉ＋３）及び
Ａ（Ｉ）とＡ （Ｉ＋１）とＡ （Ｉ＋２）がレジスタ
を共有していも このレジスタを使った疑似コードを第
１２図に水塊 さらへ ロード命令移動手続き４を行な
い（第１３図）、ロード命令生成手続き５を行なう（第
１４図）。最後へ ストア命令生成手続き６を行な（＼
この結果を示したのが第１５図であも このようＪｌ−、ループをアンロールすることにより、
ループリターン時には次のループボディの最初で用いる
レジスタがセットされているの玄 レジスタ間のコピー
が不用となも つまり、プログラム例１の場合を見ると
、 Ｉ＝３の時のループボディの最後で（戴 ｒｅｇｏ
にＢ（５）がセットさり、ｒｅｇｌにＢ（６）がセット
さり、ｒｅｇ３にＢ（４）がセットされ 次のＩ＝６の
ループボディの最初で必要となるレジスタセット（ｒｅ
ｇＯ＝Ｂ （５）、 ｒｅｇｌ＝Ｂ （６）、 ｒｅｇ
３＝Ｂ （７） ）が達成されていも 最後１−、 プログラム例２に対しても同様に行なう
ことができ、この結果を、第１６図に示す。
このよう番ζ 第１．２のコンパイル方法によりレジス
タの使用方法を変えるだけて 不用なメモリアクセスを
なくすことができも またレジスタを備えた計算機であ
れば 本実施例は適用可能であム 発明の効果 本発明（よ レジスタの割当方法を適用してレジスタ割
当方法を変えることにより、配列データの演算を含むル
ープ文の実行を無駄なメモリのアクセスをなくした分、
高速実行させることができもまた アンローリング手法
によりレジスタのムーブを省略できも
タの使用方法を変えるだけて 不用なメモリアクセスを
なくすことができも またレジスタを備えた計算機であ
れば 本実施例は適用可能であム 発明の効果 本発明（よ レジスタの割当方法を適用してレジスタ割
当方法を変えることにより、配列データの演算を含むル
ープ文の実行を無駄なメモリのアクセスをなくした分、
高速実行させることができもまた アンローリング手法
によりレジスタのムーブを省略できも
第１図は本発明の第１のコンパイル方法のフローｍ
第２図は本発明の第２のコンパイル方法のフローは 第
３〜７図はプログラム例１に対して第１のコンパイル方
法を適用した場合の説明は第８図はプログラム例１の第
１のコンパイル方法によるコンパイル結果のコード諷
第９図はプログラム例２の第１のコンパイル方法による
コンパイル結果のコード医 第１０〜１４図はプログラ
ム例１に対して第２の各コンパイル方法を適用した場合
の説明医 第１５図はプログラム例１の第２のコンパイ
ル方法によるコンパイル結果のコード医 第１６図はプ
ログラム例２の第２のコンパイル方法によるコンパイル
結果のコード＠ 第１７図はプログラム例１のＦＯＲＴ
ＲＡＮコード阻第１８図はプログラム例２のＦＯＲＴＲ
ＡＮコー１’は １１９図はプログラム例１に対する従
来例の疑似コード医 第２０図はプログラム例２に対す
る従来例の疑似コード図であも １・・・ループ箇所検出手続き、 ２・・・配列データ
検出手続き、 ３・・・レジスタ割り当て手続き、 ４
・・・ロード命令移動手続き、 ５・・・ロード命令生
成手続き、６・・・ストア命令生成手続き、 ７・・・
レジスタ間移動手続き、 ８・・・ループアンローリン
グ手続き。
第２図は本発明の第２のコンパイル方法のフローは 第
３〜７図はプログラム例１に対して第１のコンパイル方
法を適用した場合の説明は第８図はプログラム例１の第
１のコンパイル方法によるコンパイル結果のコード諷
第９図はプログラム例２の第１のコンパイル方法による
コンパイル結果のコード医 第１０〜１４図はプログラ
ム例１に対して第２の各コンパイル方法を適用した場合
の説明医 第１５図はプログラム例１の第２のコンパイ
ル方法によるコンパイル結果のコード医 第１６図はプ
ログラム例２の第２のコンパイル方法によるコンパイル
結果のコード＠ 第１７図はプログラム例１のＦＯＲＴ
ＲＡＮコード阻第１８図はプログラム例２のＦＯＲＴＲ
ＡＮコー１’は １１９図はプログラム例１に対する従
来例の疑似コード医 第２０図はプログラム例２に対す
る従来例の疑似コード図であも １・・・ループ箇所検出手続き、 ２・・・配列データ
検出手続き、 ３・・・レジスタ割り当て手続き、 ４
・・・ロード命令移動手続き、 ５・・・ロード命令生
成手続き、６・・・ストア命令生成手続き、 ７・・・
レジスタ間移動手続き、 ８・・・ループアンローリン
グ手続き。
Claims (2)
- （１）配列データを扱う演算を含んだループ文のプログ
ラムのコンパイルにおいて、プログラム中の配列データ
の検出手続きと、ループ箇所の検出手続きとを含み、前
記ループ文のコンパイル結果をループにはいる前の前処
理部分であるループエントリと繰り返す演算部分である
ループボディとループを繰り返すための後処理部分であ
るループリターンの３つの部分から成るとする時、前記
配列データのうち異なった配列名及び異なったインデッ
クスを持つものをそれぞれ別のレジスタに割り当てる手
続きと、前記配列データのうちインデックスが最大のも
の以外のものに対応する前記レジスタへのメモリからロ
ードをループエントリの前で行なう手続きと、前記配列
データのうちインデックスが最大のものに対応する前記
レジスタへのメモリからロードをループボディの中で行
なう手続きと、ループボディの中で前記配列データに対
応する前記レジスタの内容をその配列データのインデッ
クスと異なる前記配列データに対応する前記レジスタに
ムーブする手続きと、前記配列データのメモリへのスト
アが必要な時はループボディの中で少なくともインデッ
クスの最小なものをメモリへストアする手続きと、それ
以外をループリターンの後でストアする手続きとを含む
ことを特徴とするコンパイル方法。 - （２）前記レジスタへムーブする手続きを行なわずに、
前記配列データのインデックスのループ内での最大差異
値の整数倍回だけループをアンロールする手続きを含む
ことを特徴とする特許請求の範囲第１項記載のコンパイ
ル方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1290188A JPH03150636A (ja) | 1989-11-08 | 1989-11-08 | コンパイル方法 |
| US08/225,352 US6173443B1 (en) | 1989-11-08 | 1994-04-08 | Method of compiling a loop |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1290188A JPH03150636A (ja) | 1989-11-08 | 1989-11-08 | コンパイル方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03150636A true JPH03150636A (ja) | 1991-06-27 |
Family
ID=17752891
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1290188A Pending JPH03150636A (ja) | 1989-11-08 | 1989-11-08 | コンパイル方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6173443B1 (ja) |
| JP (1) | JPH03150636A (ja) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6820250B2 (en) * | 1999-06-07 | 2004-11-16 | Intel Corporation | Mechanism for software pipelining loop nests |
| KR100707781B1 (ko) * | 2006-01-19 | 2007-04-17 | 삼성전자주식회사 | 컴퓨터 시스템에서 배열 연산을 효율적으로 처리하는 방법 |
| JP5458065B2 (ja) * | 2011-07-25 | 2014-04-02 | 伸一 石田 | モジュールの構造解析を支援する装置及びプログラム |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62169272A (ja) * | 1986-01-22 | 1987-07-25 | Fujitsu Ltd | ベクトル演算列ル−プアンロ−リング処理方式 |
Family Cites Families (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4463423A (en) * | 1982-07-14 | 1984-07-31 | Burroughs Corporation | Method of transforming high level language statements into multiple lower level language instruction sets |
| US4567574A (en) | 1983-03-14 | 1986-01-28 | International Business Machines Corporation | Optimizing cobol object code instruction path length with respect to perform statements |
| JPS6123275A (ja) * | 1984-07-11 | 1986-01-31 | Nec Corp | ベクトル処理装置 |
| US4656583A (en) | 1984-08-13 | 1987-04-07 | International Business Machines Corporation | Method for improving global common subexpression elimination and code motion in an optimizing compiler |
| US4763255A (en) * | 1984-10-31 | 1988-08-09 | International Business Machines Corporation | Method for generating short form instructions in an optimizing compiler |
| US4656582A (en) * | 1985-02-04 | 1987-04-07 | International Business Machines Corporation | Generating storage reference instructions in an optimizing compiler |
| US4642765A (en) | 1985-04-15 | 1987-02-10 | International Business Machines Corporation | Optimization of range checking |
| JPS62159274A (ja) | 1986-01-08 | 1987-07-15 | Hitachi Ltd | 条件分岐の分割・複写によるベクトル化方式 |
| JP2708405B2 (ja) * | 1986-03-03 | 1998-02-04 | 株式会社日立製作所 | コンパイラにおけるループ展開方法 |
| JPH0685148B2 (ja) * | 1986-03-07 | 1994-10-26 | 株式会社日立製作所 | 配列デ−タフロ−解析装置 |
| JPH0814817B2 (ja) * | 1986-10-09 | 1996-02-14 | 株式会社日立製作所 | 自動ベクトル化方法 |
| US4802091A (en) | 1986-10-31 | 1989-01-31 | International Business Machines Corporation | Method for improving the efficiency of arithmetic code generation in an optimizing compiler using the technique of reassociation |
| JP3053092B2 (ja) | 1987-06-05 | 2000-06-19 | 株式会社日立製作所 | 並列化コンパイル方法 |
| JPH01108638A (ja) * | 1987-10-21 | 1989-04-25 | Hitachi Ltd | 並列化コンパイル方式 |
| JP2749039B2 (ja) * | 1987-11-06 | 1998-05-13 | 株式会社日立製作所 | オブジェクト生成方法 |
| US4953084A (en) * | 1987-11-16 | 1990-08-28 | Hewlett-Packard Company | Method and apparatus using variable ranges to support symbolic debugging of optimized code |
| US5121498A (en) * | 1988-05-11 | 1992-06-09 | Massachusetts Institute Of Technology | Translator for translating source code for selective unrolling of loops in the source code |
| US4991088A (en) | 1988-11-30 | 1991-02-05 | Vlsi Technology, Inc. | Method for optimizing utilization of a cache memory |
| US5202995A (en) | 1989-10-12 | 1993-04-13 | International Business Machines Corporation | Method for removing invariant branches from instruction loops of a computer program |
-
1989
- 1989-11-08 JP JP1290188A patent/JPH03150636A/ja active Pending
-
1994
- 1994-04-08 US US08/225,352 patent/US6173443B1/en not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62169272A (ja) * | 1986-01-22 | 1987-07-25 | Fujitsu Ltd | ベクトル演算列ル−プアンロ−リング処理方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| US6173443B1 (en) | 2001-01-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Weihl | Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables | |
| Der Jeng et al. | A review of synthesis techniques for Petri nets with applications to automated manufacturing systems | |
| US4969091A (en) | Apparatus for stack control employing mixed hardware registers and memory | |
| Krall | Efficient JavaVM just-in-time compilation | |
| US7185327B2 (en) | System and method for optimizing operations via dataflow analysis | |
| EP0503928B1 (en) | Method and apparatus for optimizing cost-based heuristic instruction schedule | |
| US20030041317A1 (en) | Frameworks for generation of java macro instructions for storing values into local variables | |
| US7096456B2 (en) | Method and apparatus for providing dynamically scoped variables within a statically scoped computer programming language | |
| JPH0827774B2 (ja) | 修正可能な機能をサーバ上で実行する方法 | |
| US5535394A (en) | Methods for distinguishing dynamically allocated storage along different call paths and for providing a compact representation of alias analysis | |
| KR20010093312A (ko) | 토큰 기반 링크 | |
| JP2002525707A (ja) | バーチャルコールのインライン化のための精確な方法 | |
| Grothoff | Walkabout revisited: The runabout | |
| EP0798636A1 (en) | Method and system for register allocation using multiple interference graphs | |
| US6854113B1 (en) | Mixed-mode execution for object-oriented programming languages | |
| Ekanadham | Future scientific programming on parallel machines | |
| Agrawal et al. | Interprocedural communication optimizations for distributed memory compilation | |
| US6173443B1 (en) | Method of compiling a loop | |
| JP3296027B2 (ja) | ロードストア型プロセッサの付加的レジスタを利用する際のコンパイル方法 | |
| Welch et al. | An Experiment with Recursion in occam | |
| Namashivayam et al. | OpenSHMEM as a portable communication layer for PGAS models: a case study with coarray fortran | |
| Kulczycki et al. | A specification-based approach to reasoning about pointers | |
| KR20040044655A (ko) | 자바 가상머신에서 루프 문 처리를 위해 바이트코드를생성 및 수행하는 방법 | |
| Higuchi et al. | Java bytecode as a typed term calculus | |
| Sams | Dynamic storage allocation for an information retrieval system |