JPH0656582B2 - 範囲検査の最適化方法 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、コードの品質を改良するために用いられる
最適化アルゴリズムを持つたコンパイラ、特に、範囲検
査（レンジ・チエツキング）を実行するコードを自動的
挿入するコンパイラに適用して最適なものである。さら
に詳細に言えば、この発明は、オブジエクト・プログラ
ムの実行の際に行なう必要のある範囲検査の量を少なく
することができるものであり、いくつかの場合において
は、範囲の検査されている変数が規定の範囲から外れて
ないことを最適化ルーチングが判断すると、範囲検査コ
ードを全く取り除くことができるようにするものであ
る。

この発明は、あるゆるタイプのコンピユータの最適化コ
ンパイラに適用することができるが、特に縮小命令セツ
ト・コンピユータ（ＲＩＳＣ）に有用である。なぜなら
ば、この縮小命令セツト・コンピユータの各命令はより
単純でより簡単な機能を実行するので、コンパイラで生
成されるコードは複雑な命令セツトのコンピユータに対
して生成されるコードよりも、しばしばより大量とな
る。さらに、縮小命令セツト・コンピユータにおいて
は、しばしばコンピユータに組込まれるメモリ保護ハー
ドウエアが少ない。メモリの完全性を保護するためにこ
のような縮小命令セツト・コンピユータのコンパイラ
は、アドレシングが規定の領域内に留まることを保障す
るコードを挿入する。このようなコードは、この発明に
より最適化することができる。したがつて、ソフトウエ
ア・メモリ保護のコストが減少する。

コンパイラにより生成されるコードの品質は、最初のコ
ンパイラが作られた時以来ずつと問題となつていた。商
業的に入手可能な最初のコンパイラであるフオートラン
Ｉコンパイラの主な目的の１つは、コード品質の点でア
センブリ言語プログラムにより作成されたものと匹敵す
るオブジエクト・コードを科学計算の分野において生成
することであつた。

今日では、高レベル言語はコンピユータが適用できるあ
らゆる分野において使用できるように設計されている。
初期のフオートラン言語でさえ広範囲のプログラミング
の仕事に適用できるように意図されていた。しかしなが
ら、コンパイラで生成されたコードが高品質であること
もなお重要なことである。特に生成されたコードが製造
環境で使用されるものであるときは一層重要である。熟
練したアセブリ言語プログラマにより作成されたコード
は、今でもどのコンパイラで作成されたコードが適用さ
れるかについての基準となつている。

１９５０年代から、コンパイラで生成されたコードの品
質を改良するために多数の最適化技術が開発され、改良
されてきた。実際に、これらの最適化技術の多くは原理
的に知られていて最初のフオートラン・コンパイラを作
成したチームによりある程度使用されていた。

最適化コンパイラにおいてしばしば用いられる最適化技
術は、共通な下位表現の削除、高実行頻度領域から低実
行頻度領域にコードを移すこと（コード移動）、無用コ
ードの削除、ストレングスの減少（遅い操作を同等の速
い操作に置き換えること）、そして一定の伝搬である。
これらの最適化の説明が次に述べられている。

ジユー・テイー・シユワルツ、「プログラミングについ
て、ＳＥＴＬ言語についての中間報告、第二巻：ＳＥＴ
Ｌ言語およびその使用例」、クーラント・インステイテ
ユート・オブ・マスマテイカル・サイエンス、ＮＹＣ
（１９７３）、ＰＰ２９３−３１０（J.T.Schwartz On
Programming An Interim Report on the SETL Languag
e. Installment II：The SETL Language and Examples of
Its Use.Courant Institute of Mathematical Science
s、NYC（１９７３）、PP２９３−３１０。） エー・アホおよびジエー・ウルマン、「コンパイラ設計
の原理」、アデイソンーウエズレイ（１９７７）、（A.
Aho,and J.Ullman,Principles of Compiler Design,Add
ison Wesley,（１９７７）。

〔従来の技術〕

範囲検査の最適化は比較的新しい概念であり、上述の文
献では扱われていない。一般的な概念については以下の
論文「範囲検査の最適化」においてすでに出版されてい
る。しかしながら、この論文において開示されている範
囲検査の最適化技術は、ある制御フローの場合に間違つ
たコードを発生するという重大な欠陥を有することが知
られている。この発明は、この出版された論文の最適化
技術の欠陥を解決するものである。この従来技術の論文
は、以下を参照されたい。

ブイ・マークスタイン、ジエー・コツクおよびピー・マ
ークスタイン、「範囲検査の最適化」、コンパイラ構造
に関するSIGPLAN（１９８２）シンポジウムの論文、Ｐ
Ｐ１１４−１１９、エー・シー・エム注文番号５４８８
２０、ボルテイモア、エム・デー（V.Markstein,J.Cock
e and P.Markstein,Optimization of Range Checking P
roc.of the SIGPLAN（１９８２）Symposium on Compile
r Construction,PP１１４−１１９，ACMOrder Number５
４８８２０，Baltimore,MD）。

範囲検査または変数の範囲の解析を特別に取扱つている
他の文献は： ダブリユー・ハリソン、「変数の値範囲のコンパイラ解
析」、アイ・イー・イー・イー、トランザクシヨン・オ
ブ・ソフトウエア・エンジニアリング、（１９７４．
５）；PP２４３−２５０ （W.Harrison,Compiler Analysis of the Value Ranges
for Variables,IEEE Transactions of Software Engineering,(May１９７
４）；PP２４３−２５０） ジエー・ウエルシユ、「パスカルにおける経済的な範囲
検査」ソフトウエアー練習と経験、（１９７８）：Vol.
８，PP８５−９７（J.Welsh,Economic Range Checks in
Pascal Software-Practice and Experience,（１９７
８）：Vol.８，PP８５−９７）。

ハリソンの論文は範囲検査の最適化の主題については触
れていない。彼はこの発明がその目的を達成するのに用
いる１つの技術となる範囲解析を説明している。ハリソ
ンの範囲解析は、この発明の方法よりも複雑であり、こ
の発明で意図されるよりもより複雑な状態での範囲解析
ができる。もし、ハリソンの範囲解析技術がこの発明と
結びつけられるならば、ずつと複雑でかつ実施するのは
困難であるけれどもここに開示されるものよりもより強
力な範囲検査最適化技術が得られるであろう。

ウエルシユの範囲検査最適化技術は、パスカル・プログ
ラミング言語中のデータ構造宣言の性質およびそのプロ
グラミング言語中の表明の含意に強く依存している。彼
の範囲検査最適化は構文および意味解析の際に実行する
ことができる。これは、この発明のように一般的な制御
フローの場合には対処することができない。

〔発明が解決しようとする問題点〕

この発明の主な目的は、命令ストリーム中で一つの入口
を持つ強く結合された領域（ＳＣＲ）から、範囲検査計
算を取り除くため最適化コンパイラ中で実行できる方法
を提供することである。ここで、範囲検査命令は、制御
がＳＣＲの中に留まるかどうかを制御する誘導変数に線
型に関係づけられた比較値（コンパランド）を含んでい
る。

この発明の別の目的は、一つの入口を持つ強く結合され
た領域のヘツダー・ノード中に、最初の繰返しの間に範
囲検査が失敗してしまつたかどうかを決定するための範
囲検査命令を置く方法を提供することにある。

この発明の他の目的は、誘導変数がその期待される最終
値に到達したかどうかを判定することによりＳＣＲが正
しい回数だけ実行されたことを確かめる方法を提供する
ことである。

この発明の他の目的は、強く結合された領域（ＳＣＲ）
からの唯一の出口が誘導変数のテストに基づいた条件付
き出口である場合に、正しい最適化されたコードを生成
する方法を提供することである。

この発明の他の目的は、誘導変数のテストに基づいた１
つの条件付出口と、誘導変数を含まない付加的な条件付
出口とが存在する場合に、正しい最適化されたコードを
生成する方法を提供することである。この付加的な条件
付出口は、強く結合された領域の中のどこの場所で生じ
てもよい。

この発明のさらに他の目的は、一つの入口を持つ強く結
合された領域またはループの外へ、ある範囲検査命令を
移して命令の線型領域へ置くことにより、プログラムの
正確さを失なわずに計算効率を高める最適化コンパイラ
中の最適方法を提供することにある。要するに、この方
法は、もし強く結合された領域（ＳＣＲ）から唯一の条
件付出口が存在する場合にＳＣＲのヘツダー・ノード中
に範囲検査トラツプ命令を置くこと、誘導変数Ｖの値に
基づいた条件付出口テストを修正すること、誘導変数が
元（修正されていない）のプログラムで得られたであろ
う値に達することを確実なものとするためにループの出
口ポイントに新しい検査を挿入することを含む。

以下のこの発明の説明をわかりやすくするために、マー
クスタン、コツクおよびマークスタインらによる上述の
論文中で主張された範囲検査最適化を最初に説明する。
説明を簡単にするために次の用語を定義する。

（定義） 部分グラフ：ここで用いられる部分グラフという表現
は、プログラムの全体のフロー・グラフのノード（節）
の部分集合と、部分集合内のノードを接続するフロー・
グラフの枝（エツジ）とを示す。

強く結合された領域：強連結領域ともいう。どの節点も
自分自身が先行点であり、同時に、後続点であるような
節点の集合をいう。

一つの入口を強く結合された領域（ＳＣＲ）：上記強く
結合された領域のうち、その外に先行ブロックを有する
ノードが唯一存在するものをいう。以下、本願明細書に
おいてはこれを頭文字ＳＣＲ（strongly connected reg
ion）をもって表す。プログラム上、ＳＣＲはループと
して観念される。

ＵＳＥ機能：あるプログラムポイント（プログラムにお
いては一行の「命令」に相当するもの）に対するＵＳＥ
機能はそのプログラムポイントにおける変数または定数
がオペランドとして用いられている全てのプログラムポ
イントを特定する。

ＤＥＦ機能：ＤＥＦ機能実行の対象となったオペランド
が変数として、あるいは、定数として使用されているプ
ログラムポイントの集合を与える。

領域定数：ＳＣＲ中で計算がされない、すなわち、一定
の状態に存在する数のこと。すなわち、ある領域定数に
対してＤＥＦ機能を実行すれば当該ＳＣＲ中では該当す
るプログラム・ポイントが存在しない。

誘導変数：ＳＣＲ中で誘導変数Ｖに対してＤＥＦ機能を
とると、一のみのプログラムポイントを有するものであ
る。つまり、該ＳＣＲ中で一回だけ計算され、以下の計
算式にしたがって一定数増分される数のことをいう。

Ｖ＝Ｖ＋ｒｃ（ｒｃ：領域定数） 範囲検査：誘導変数を領域定数と比較する操作であっ
て、その比較の結果が「真」である場合には実行を打ち
切るもの。

入口ノード：ＳＣＲ中の入り口ノードとは、ＳＣＲ中に
含まれない先行ブロック（プレデセサー）を持つＳＣＲ
内の唯一のノードである。

ヘッダー・ノード：ＳＣＲ中のヘッダ・ノードは前記入
口ノードの唯一の先行ブロックであって、該ＳＣＲ中に
含まれないノードをいう。もし、ＳＣＲがへっだ・ノー
ドを含んでいなければ、当該技術に詳しいものには明ら
かなように、制御フロー・グラフはヘッダ・ノードを有
する等価の制御フロー・グラフに容易に変更することが
できる。

アーテイキュレーション・ノード：部分グラフの全ての
なぞり（トラバーサル）において訪れられるノードをい
う。すなわち、当該アーテイキュレーション・ノードは
プログラム実行をその部分グラフについて行えば、領域
定数、誘導変数の状態にかかわらず必ず実行の対象とな
る部分である。

トラツプ命令： トラツプ命令とは、範囲検査を符号化するために用いら
れる中間言語である。トラツプ命令は２つのオペランド
ＸおよびＹと比較式Ｒを指定する。もし、比較式： ＸＲＹ が誤りならば、プログラムは終了する（なぜならば、範
囲条件が違反されたから）。そうでなければ、プログラ
ムは次の順番の命令に進む。トラツプは、条件付ジヤン
プまたはエラー・ルーチンの呼出しが後につづく通常の
比較命令により最終コード中に実現されてもよい。

〔実施例〕

この発明の目的は、一般に、プログラム・ループから範
囲検査トラツプ命令を取り除き、そしてこの命令を命令
ストリームの線形部分に置くことにより、実行の頻度を
大いに減少させ、その結果としてコンパイルされたプロ
グラムの実行効率が顕著に改良される、最適化コンパイ
ラ中で操作可能な手順によつて達成される。より詳細に
は、この手順は、誘導変数に基づかない条件付出口が後
に続く、誘導変数に基づいた条件付出口により特徴づけ
られたループの箇所でプログラムを適切に再コーデイン
グすることを含む。この手順は、範囲検査のためのトラ
ツプ命令を中に有する命令ストリーム中のループまたは
一つの入口をもつ強く結合された領域（ＳＣＲ）を識別
することを含む。このトラツプ命令は誘導変数Ｖと領域
定数とを比較する。誘導変数Ｖは次の３つの条件を満足
しなければならない： １）Ｖはループ中で一回のみ修正される。２）ループ中
でのＶの修正はアーテイキユレーシヨン・ノード中にお
いてである。３）Ｖを領域定数と比較することによりル
ープから出る条件付出口Ｃが一つだけある。そこで、ト
ラツプ命令をループから取り出してＳＣＲのヘツダ・ノ
ード中に置くことができる。制御がループ中に留まつて
いる限りトラツプＴがプログラムの終了を生じないこと
を確実にするため、Ｖに基づく条件付出口Ｃの比較値を
修正する必要がある。これを達成するために、第２のト
ラツプ命令をＳＣＲの出口（ループの中ではない）に置
かなければならない。

もしＣからの路（パス）が直接に入口ノードに行くなら
ば、または、もしＣから入口ノードへの路（パス）上に
他の条件付出口がなければ、ＳＣＲから出るＣからの路
（パス）上に前記第２のトラツプ命令が挿入されなけれ
ばならない。この命令はもし誘導変数Ｖがループ出口の
ための元の条件Ｃを満足しなかつたら終了を行う。

一方、Ｃと入口ノードの間に他の条件出口が存在する場
合もある。この場合は、出口パス上に新たな条件付き分
岐が設けられなければならない。この条件付き分岐はｖ
が元のループの出口条件Ｃを満たす時は直接出口へと導
かれるものである必要がある。また、当該出口へ向かう
パス上に、該ループ内にあってＣと入口ノードの間にあ
る全てのパス上に存在するコードをコピーし、挿入する
必要がある。ただし、このコピーされたすべての条件付
き分岐（または、単なる分岐の場合もある）のうち、元
のプログラムにおいて入口ノードにをその行き先として
分岐していたものについては、その行き先が新たに挿入
されるトラップ命令に変更される。このトラップ命令に
よってプログラムはその実行停止が保証される。

ＳＣＲ中でトラツプとして符号化された範囲検査は、も
し誘導変数Ｖの値に基づいたＳＣＲからの条件付出口が
存在するならば、次の過程により取り除くことができ
る。オペランドの１つが誘導変数Ｖか、または、誘導変
数の線型関係であるＳＣＲ中のトラツプが存在し、この
トラツプがアーテイキユレーシヨン・ノード中に生ずる
と仮定する。この場合、以下の操作によってトラップ
を、ＳＣＲ中から取り除くことができる： ステツプ１：トラツプ命令のコピーがヘツダ・ノード中
に置かれる。

ステツプ２：誘導変数の値に基づいたＳＣＲからの条件
付出口が１つのみ存在するがどうかを判断する。

ステツプ３：もしＳＣＲ中のコードがもう１回の繰り返
し実行された場合にトラツプがプログラムを終了させな
いことを保証するために、誘導変数Ｖの値に基づいたＳ
ＣＲからの条件付出口が修正される。これは、ＳＣＲか
らの出口路にすすむべきぶかどうかを決定するために誘
導変数が比較される相手となる定数値たる比較値を変更
することを含む。もし、トラツプが次の形式： もしＶが限界（limit）よりも大きければ、打ち切る。
（ａ） であり、そして、ループの閉成条件が次の形式： もしＶがｍより小さいか等しければ、繰り返す。（ｂ） であるならば、ヘツダ・ノード中に次の計算を挿入
し、： ｔ＝min(limit,m)（ｃ） なお、ここでmin(limit,m)とはlimit,mのうち小さい方
を選択する操作である。そして、そして、ループの閉成
条件を次の通りに変更する： もしＶがｔより小さいか等しければ繰り返す： 同様の変換が、当該技術に詳しいものに明らかのよう
に、トラツプおよびループ閉成条件中の比較式の組合せ
に対して容易に実行できる。１つのささいな変形は次の
通りである： もしＶが限界（limit）よりも大きいか等しければ、打
ち切る。（ａ） もしＶがｍよりも小さいか等しければ、繰返す。（ｂ） ｔ＝min(limit-1,m)（ｃ） ステツプ４：誘導変数が元のプログラム、すなわち、上
述の修正を受ける前のプログラム、において得たであろ
う値に到達していることを保証するために、ループの出
口ポイントに追加の検査が挿入されなければならない。
前のステツプで示された場合に関しては、検査は次の様
になる： もしＶがｍより小さいか等しければ、打ち切る。

変換されたプログラムが元のプログラムと同等なもので
あるかどうかを見るために、もし元のプログラムが最初
の繰返しで範囲検査を失敗していたならば、変換された
プログラムはヘツダ・ノード中に挿入された範囲検査を
失敗する。逆に、もし変換されたプログラムがヘツダ・
ノード中に挿入された範囲検査を失敗するならば、元の
プログラム中の範囲検査はアーテイキユレーシヨン・ノ
ード中に存在するので元のプログラムは最初の繰返しで
範囲検査を失敗していたであろう。変換されたプログラ
ムは、その後はループ出口ポイントで挿入された範囲検
査上でのみトランプすることができる。しかしこのよう
なトランプは、誘導変数がその期待された最終値に達し
なかつたことを示している。元のプログラムにおいて
は、ループの追加的繰返しが生じていたであろう。そし
て、この繰返しの１つは範囲検査を失敗させてしまつて
いただろう。

マークスタイン、コツクおよびマークスタインの論文
は、どのように条件付出口を修正するか、そして、どの
ようにプログラム出口に新しい検査を挿入するかを記述
している。すなわち、ループに入る前に１つのトラツプ
を実行し、そのループから出た後で１つのトラツプを実
行することにより、ループ（高実行頻度の領域である）
中のトラツプを取り除くことができる。論文のページ１
１６−１１７では、誘導変数と独立なＳＣＲからの出口
が存在するならば、この出口は解析に何の影響を有しな
いことを観察している。第３図に示めされるようなフロ
ー・グラフに対して、この観察は正しい。これらのフロ
ー・グラフは追加のループ出口で特徴づけられるが、こ
れらの出口を取るかどうかは誘導変数を必要としない。
さらに、これらの出口決定は、誘導変数に基づく出口決
定に出会う前のループのなぞり（トラバーサル）の際に
起こる。

しかし、ＳＣＲ入口ノードと誘導変数に基づいたループ
出口との間の制御フロー路上に、誘導変数に基づかない
ループ出口が存在しているケースは考慮されなかつた。
第５図はこの状態の特徴を表わしている。ブロツク１で
トラツプが生じ、そしてブロツク２で誘導変数がテスト
されると仮定する。もし、誘導変数がある値に達する
と、制御はＳＣＲを去りブロツク４に進む。論文のアル
ゴリズムは、ブロツク２中のテストを変更してブロツク
１中の範囲検査が終了を生ずることができないよう保証
することを教えている。これはなお正しい。

しかしながら、上述されたステツプの最後で、テストが
ブロツク２からブロツク４への路上に挿入されることを
要求する。このテストは、もしブロツク２が変更されな
かつたらば達していたであろう値に誘導変数が到達して
いることをテストするものである。これは、前記ブロツ
ク２における誘導変数に関するテストとループ出口との
間に他のテストが存在しない場合にのみ正しい。

第５図に示されているＳＣＲにおいて、前記誘導変数が
所期の最終値に達する前にブロック３に係わるテストに
よってループ外に実行が移される場合がありえる。すな
わちどういうケースかというと、前記誘導変数が次のル
ープ実行に際して範囲検査の結果「真」であると判定さ
れるが（すなわち、ｖ＞ＬＩＭＩＴ）、同時に誘導変数
がいまだ所期の最終値に達していないような場合である
（ｖ＜ｍ）。第６図ブロック２と４の間に挿入されたテ
ストは、修正前のプログラムにおいてはかかる場合にト
ラップがループ中で実行されることから、これと等価な
構造とするために設けられたものである。しかしなが
ら、上記のケースは修正前のプログラムにおいて、前記
誘導変数は次のループ実行がされれば範囲外となるもの
であっても、実際はブロック３に係わる別のループ出口
条件が存在するために次のループ実行がされないケース
であることも考えられる。このケースの場合は前記ブロ
ック２と４の間に挿入されたテストでは修正前のプログ
ラムを忠実に表現するものではない。なぜならば、第６
図のような変換では上記のケースにおいては、本来修正
前のプログラムにおいては実行されえないループ実行が
なされてしまうためである。この点で、前記論文の変換
は正しいものではない。

第１図は最も簡単なＳＣＲを示す。マークスタイン、コ
ツクおよびマークスタインの論文は、このようなフロー
・グラフをどのように処理するかを正確に記述してい
る。そして、第２図はこの論文に記載された手順に従つ
た範囲検査最適化の結果を示す。

上記の従来技術の箇所で説明されたステツプ４を修正す
ることを除いて、この発明は上述されたマークスタイ
ン、コツクおよびマークスタインの論文により与えられ
た全体の手順に従うトラツプ最適化を正確に実行する。

この発明によれば、上記の論文に開示された元のステツ
プ４（参照のために下に再度示す）を次の様に修正す
る： 元のステツプ４：元のプログラム、すなわち上述の修正
が行なわれる前、において得られたであろう値に誘導変
数が達していることを保証するために、ルイープの出口
ポイントにおいて追加的な検査を挿入しなければならな
い。前のステツプ（前述された例のステツプ３）で示さ
れた場合に対して、検査は： もしＶがｍよりも小さいか等しければ、打ち切る。

である。

新ステツプ４：ＳＣＲの入口ブロツクと条件付出口との
間に他のテストが存在しないならば、誘導変数に基づい
た条件付出口からＳＣＲの外のノードへの路（パス）上
に、元のプログラムにおいて得られたであろう値に誘導
変数が達していることを保証するテストが置かれなけれ
ばならない。もし誘導変数がその所期の最終値に到達し
ていなかつたならば、修正された条件付出口命令が次の
繰返しを防止するためである。なぜならば、次の繰返し
においてトラツプ命令は範囲検査違返の理由でプログラ
ムの終了を惹き起こしているであろう。

もしＳＣＲの入口ブロツクと条件付出口との間に他の条
件付出口が存在するならば、誘導変数に基づいた条件付
出口から出口ノードへの出口路に沿つて、２つの項目が
付け加えられなければならない。第１に、誘導変数がそ
の所期の値に到達したかどうかを確かめるテストが挿入
される（第７図のノード３′）。

すなわち、もし誘導変数Ｖが所期の値に達するならば、
元のプログラムは出口ノードにブランチしているはずな
ので、修正されたプログラムもそうあるべきである。第
２に、誘導変数に基づいた条件付出口と入口ノードとの
間の部分グラフが出口路に沿つてコピーされなければな
らない。元のプログラムにおいて誘導変数がその最終値
に達する前に他の条件付出口の１つからループ出口が発
生してしまうかもしれないから、このコピーは必要であ
る（第７図のノード３″）。しかし、元のグラフで入口
ノードに導く枝（エツジ）の所では、コピーされたグラ
フではプログラム終了に導く枝でなければならない。換
言すれば、コピーされたコード中でループへ戻る試み
は、ループの次の繰返しにおける範囲検査を表わさなけ
ればならない（第７図中のノード３）。第７図は、範
囲検査の最適化が実行される場合、第５図のフロー・グ
ラフがどのように修正されなければならないかを示す。
第１図から第７図に関して前述されたこの発明の説明に
より、当該技術に明るい者がここで開示された発明を適
当な最適化コンパイラに組込むことができる程度のこの
発明が十分かつ完全に開示された。第１図から第７図ま
では、この発明が適用される例である。これらの図は、
この例がこの発明によりどのように変換されるかを示し
ている。

第８図から第１１図までは、この発明を実行するのに必
要な詳細な操作を説明する従来技術をも含むフロー・チ
ヤートである。

これらの図において、第８図は周知の従来の最適化コン
パイラの高レベルのフロー・チヤートである。ブロツク
１、２、４、および５は全く自明であり良く知られてい
る。“コード最適化”と称されるブロツク３は、この発
明が適用されるコンパイラの活動のフエーズであり、第
９図に詳細に示されている。

第９図は、このような最適化コンパイラに対するコード
最適化フエーズのフロー・チヤートである。ブロツク１
および４で実行される操作は自明であり良く知られてい
る。“包括的な共通下位表現の削除およびコード移動”
と称されるブロツク２は一般によく知られている最適化
フエーズに関する。しかしながら、この形式の最適化を
達成する特別な方法については、１９８４年８月１３日
米国で特許出願されたシリアル番号６４０２８３号“最
適化コンパイラにおける改良された包括的な下位表現の
削除およびコード移動の方法”を参照されたい。“範囲
検査の最適化”と称されたブロツク３は、この発明が適
用される最適化コンパイラの特別な領域である。このブ
ロツクは第１０図および第１１図に拡大されて詳細に説
明されている。ブロツク３の位置は、他の最適化と関連
して範囲検査の最適化がどこで実行されるべきかを示し
ている。領域定数の実際の値が知られている場合は、ヘ
ツダー・ノードおよび出口ノードに挿入されるいくつか
の命令の結果を決定することが可能である。これによれ
ば、最終コードを非常に簡単化することができる。この
単純化の実行は、全体的な一定の伝搬および不要コード
の削除（ブロツク４）の仕事である。この発明の中に前
述したように一定の伝搬および不要コードの削除をここ
で組込むことはしない。これは発明の内容をわかりにく
くするだけである。

第１０図は、この発明の範囲検査最適化の特徴を示す高
レベル・フロー・チヤートである。図のブロツク１およ
び２は、ＵＳＥ機能およびＤＥＦ機能を決定し、ＳＣＲ
を識別してリストすることを含む。容易に理解されるよ
うに、これらの機能は例えばどこでＳＣＲが始まり終る
かを決定するために、中間言語命令のリストを検査し、
そして各命令の性質を見ることにより容易に達成するこ
とができるであろう。ＵＳＥおよびＤＥＦ機能は、種々
の命令に対して指定されたオペランドを検査することに
より決定されるであろう。容易に理解されるように、こ
れら２つの機能は、全体のコンパイラの流れの中で早め
に又は第９図のブロツク３中に示されるように別に達成
されることができる。

ブロツク３は、コンパイルされている特定のプログラム
に対して識別されたすべてのＳＣＲが範囲検査最適化の
可能性に関して処理されたかどうかを決定する単なるテ
ストである。ＳＣＲの候補が存在する限り、処理テスト
からその特定のＳＣＲが除去される所であるブロツク４
までシステムが進行する。その処理の最初のステツプ
は、ＳＣＲの全てのアーテイキユレーシヨン・ノードが
識別されてマークされる所であるブロツク５で実行され
る。そして、システムは、この発明が適用できる前に必
要な３つの特定の条件を満足する誘導変数ＶがＳＣＲに
含まれるとどうかを確認するための決定が行なわれるブ
ロツク６に進む。これらの３つの条件は、図のブロツク
６中に示めされているが参照のためにここに繰り返す。
これらは： １．誘導変数ＶがＳＣＲ（Ｓ）中で正確に一回修正され
る。

２．ＳＣＲ中の誘導変数Ｖの修正がアーテイキユレーシ
ヨン・ノード中においてである。

３．誘導変数Ｖと領域定数と比較することにより発生す
るＳＣＲ（Ｓ）からの一つの条件付出口（Ｃ）が正確に
存在する。

もし、ＳＣＲ中にそのような誘導変数が見つかななけれ
ば、システムはブロツク３に戻り、次のＳＣＲにアクセ
スする。

もし、ブロツク６のテストが肯定であるならば、システ
ムはブロツク７に進む。このブロツクは、誘導変数Ｖを
領域定数と比較するＳＣＲ（Ｓ）のアーテイキユレーシ
ヨン・ノードの１つの中に、トラツプ命令（Ｔ）が存在
するかどうかを決定する。もしなければ、この発明が適
用されないのでシステムは再びブロツク３に戻る。もし
テストが肯定ならば、第１１図に詳細に示めされるブロ
ツク８にシステムが進む。このブロツクの全体の機能
は、ＳＣＲからトラツプ命令を取り除くこと、トラツプ
命令をそのＳＣＲのヘツダ・ノード中に置くこと、元の
プログラムにおいて特定された全ての条件が適切にテス
トされたかどうかを保証するためにＳＣＲからの必要な
出口（ループ中ではない）に追加の命令を挿入すること
であることを明確に理解すべきである。

第１１図を参照すると、この手順は、第１０図中のブロ
ツク８へしたがつて第１１図のブロツク１へ制御フロー
を導く第１０図に詳述された条件を満足する誘導変数お
よび範囲検査を持つた特定ＳＣＲは見つかつていること
が決定された時、活性化される。第１１図中の手順にお
いて、元のプログラムのＳＣＲ（Ｓ）を修正する詳細が
以下に説明される。

最初に行なわれる操作は、トラツプ命令ＴをＳＣＲ
（Ｓ）のヘツダー・ノード中にコピーすることである。
したがつて、適切に修正されたプログラムを表わす第
２、４、７図中においてこの命令は、範囲検査：「もし
ＶがＬＩＭＩＴより大きければ、打ち切る」として示さ
れる。ブロツク２に進むと、制御がループ中に留まつて
いる時にトラツプ命令Ｔがプログラムの終了を惹起こさ
ないことを保証するために、誘導変数Ｖに基づいた条件
付出口Ｃが修正されることをこのステツプが保証する。
ループの実行が繰り返されると、後のループの実行の際
にＴがプログラム終了を生ずるかもしれないように、誘
導変数が増加する。ブロツク２はＴが終了を惹起こすこ
とができないようにループを修正し、したがつてブロツ
ク３の活動を調整する。第１、３、５図に示された例に
おいては、これは第２、４、７図に示されるヘツダー・
ノード中で計算される新しい領域定数ｔを作ることによ
り達成される。この新しい領域定数は次のように示され
る： ｔ＝min(m,ＬＩＭＩＴ） 次に、ブロツク３でトラツプ命令ＴがＳＣＲ（Ｓ）から
取り除かれる。そしてシステムはブロツク４に進み、こ
こでＳＣＲ（Ｓ）に留まつている条件付出口Ｃから直接
に入口ノードにプログセム・フローが行くのかどうかに
関して決定が行なわれる。このブロツクが適用される特
定の出口Ｃは、ブロツク２中で特定された誘導変数Ｖを
含むものである。第１、３図に示される例においては、
Ｃからの路は直接に入口ノードに行つている。この結
果、システムはブロツク５にブランチする。第５図にお
いて示される例においては、プログラム・フローが条件
付出口“２”から入口ノード“１”に戻るのではなく、
代りにノード“３”に進むことに気がつくであろう。

第５図の例の場合のＳＣＲは、システムをブロツク６へ
進ませる。

最初にブロツク５へ進むシステムの可能性を考慮する
と、ブロツクは、誘導変数Ｖがループ出口のための元の
条件Ｃを満足しない場合にプログラムの終了を惹起する
トラツプ命令をＳＣＲ（Ｓ）を去るＣからの路上に挿入
する。第２、４図に示される例のコンパイルされたプロ
グラムの場合、この新しい範囲検査は「もしＶがｍより
大きければ、打ち切る」である。前述したように、ルー
プの外で再度のこの範囲検査は、第１０図のブロツク３
で取り除かれたトラツプの結果により元のプログラムで
もう一度ループを繰り返えさせて、次の繰り返しにおい
て終了してしまうプログラミング・エラーに対して保証
している。

第１１図のブロツク６に戻ると、他の追加的な出口がＣ
から入口ノードへの路上に存在するかどうかを見るテス
トが行なわれる。もし、条件付出口から条件付出口でな
い入口ノードへの戻りループ中に他のノード操作が存在
するならば、上述したようにシステムはブロツク５に戻
る。しかし、第５図の例のようにこの発明が特に適用さ
れる場合では、システムはブロツク７に進む。

このブロツクにおいて、もし誘導変数Ｖがループ出口の
ための元の条件Ｃを満足するならば、条件付ブランチが
出口ポイントへの出口路上に挿入される。これは第７図
中のノード“３′”により表わされる。

そして、プログラム・フローはブロツク８に進む。条件
Ｃから入口ノードに到達されることのできたコードが出
口路上に挿入される。しかし、コピーされたコード中
で、元のコードがＳＣＲの入口ノードへの路を提供する
所では、この路はプログラム終了へ導かれなければなら
ない。コピーされたコードへのこの変化の理由は、修正
された条件付出口命令Ｃにより出口路に到達することに
より、ヘッダ・ノードへの戻りは次の繰り返しにおいて
プログラムの終了に導くことが知られているからであ
る。しかし、ループＳ内からトラツプＴが取り除かれて
いるので、プログラムの終了の目的のためにループＳの
外に代替の機構が設けられなければならない。

ブロツク８がプログラム中に追加的なコードを挿入する
けれども、この追加的なコードは強く結合された領域Ｓ
の外にあり、ループＳが実行されるたび毎に１回実行さ
れるだけであることを思い出すべきである。一方、ルー
プＳの内部からトラツプＴを除去することが真の効率の
改良を生ずるために、ループＳ中のコードは数回なぞら
（トラバース）れる。

第５、７図を見ると、第７図中のノード３″は第５図の
ノード３のコピーであるが、第５図中で３からの枝（エ
ツジ）がヘツダ・ノード１へ行くところではどこでも、
第７図中の対応する枝（エツジ）がプログラムの終了を
生じさせることを保証された範囲検査（ノード３）へ
行く。

【図面の簡単な説明】

第１図は最も単純なプログラム・ループ（ＳＣＲ）のフ
ロー・グラフである。第２図は範囲検査がループから取
り除かれた第１図の同等のプログラム・シーケンスのフ
ロー・グラフである。第３図は追加の条件付出口を持つ
たＳＣＲのフロー・グラフである。第４図は第３図のＳ
ＣＲに範囲検査最適化を適用することにより得られたフ
ロー・グラフを示す。第５図は正しいプログラムが間違
つたプログラムに誤まつて変換される、誘導変数に基づ
いた条件付出口の後に条件付出口を持つＳＣＲのフロー
・グラフである。第６図は第５図のフロー・グラフが従
来技術の論文により誤まつて変換された場合のフロー・
グラフである。第７図は第５図のフロー・グラフがこの
発明により変換された場合のフロー・グラフである。第
８図はこの発明が適用されるコード最適化フエーズを含
むコンパイラの高レベルのフロー・チヤートである。第
９図はこの発明が適用されるコンパイラのコード最適化
フエーズの高レベルのフロー・チヤートである。第１０
図は範囲検査最適化の高レベルのフロー・チヤートであ
る。第１１図は１つの入口を持つ強く結合された領域か
ら範囲検査を取り除くことが要求される処理の高レベル
のフロー・チヤートである。

Claims (3)

【特許請求の範囲】
1. 【請求項１】一の範囲検査トラップ命令、一の誘導変数
   に基づいた条件付き出口および一以上の誘導変数に基づ
   かない条件付き出口とを少なくとも具備し、前記誘導変
   数に基づいた条件付き出口と前記強く結合された領域の
   出口ノードとの間に前記一以上の誘導変数に基づかない
   条件付き出口が存在する一つの入り口を有する強く結合
   された領域（ＳＣＲ）から前記範囲検査トラップ命令を
   取り出す最適化コンパイル方法であって、 前記範囲検査トラップ命令を前記強く結合された領域の
   ヘッダ・ノードに置くステップと、 前記誘導変数の値に基づいた条件付き出口のテストを修
   正するステップと、 前記強く結合された領域の出口ポイントに前記範囲検査
   トラップ命令と別の範囲検査トラップ命令を挿入するこ
   とによって、誘導変数が元のプログラムで到達すべきで
   あった値に到達していることを確認するステップと、 前記誘導変数に基づいた条件付き出口と入口ノードの間
   の部分グラフを複写するステップと、を含む最適化コン
   パイル方法。
2. 【請求項２】前記確認するステップにおける前記別の範
   囲トラップ命令は前記誘導変数に基づかない条件付き出
   口にかかわる領域定数に関するものであることを特徴と
   した請求項１の最適化コンパイル方法。
3. 【請求項３】最適化コンパイルの対象を特定するため
   に、前記ＳＣＲが、 （１）前記誘導変数が前記ＳＣＲ中で正確に一回修正さ
   れること、 （２）前記ＳＣＲ中の前記誘導変数の修正がアーテイキ
   ュレーション・ノード中にあること、 （３）前記誘導変数と領域定数とを比較することにより
   生じる前記ＳＣＲからの条件付き出口が一つのみ存在す
   ること、 を具備するものであることを特定するステップを、 さらに含む請求項１または２の最適化コンパイル方法。