JPH02238528A - コンピュータ・プログラムの第一バージョン処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明はコンピュータ・プログラムのコード翻訳分野に
関する。

［従来の技術］ 歴史的に見て、ＦＯＲＴＲＡＮ，ＣＯＢＯＬ及びＰＬ／
１等の高度なコンピュータ・ソース言語はプログラミン
グを容易にするばかりでなく、プログラムがマシンから
独立した言語で書き込まれ、その後、コンパイラにより
マシン依存性の目的コード形態に翻訳されるようにする
ことによって、種々のコンピュータ間に移動可能とする
ように開発された。従って、コンピュータの使用者や供
給者はソフトウエア・システムの開発に当たり、（しば
しば膨大な）調査を行い、その調査の利益を失わずに自
己のコンピュータ・ハードウェアを比較的安い費用でグ
レードアップする手段を講じていた。

しかしながら、コンパイラ技術は完全な解決策ではない
。例えば、あるプログラムに対するソースコードは、そ
れを所有する当事者がそれの再コンパイル（再編集）を
有効とすることを望まない場合や、旧式プログラムの場
合それが単に失われてしまっていて、利用できないこと
がある。更に、種々のハードウェア構成間の非同一性を
解決することはコンパイラ技術の範囲を越えていること
がある。コンパイラの基本機能は、あるプロセッサと他
のプロセッサとのセマンティック（意味）及びシンタッ
クス（構文）の違いを分析することであって、コンピュ
ータ・ハードウェアやオペレーティング・システムの特
有な特色の違いを分析することではない。例えば、ある
コンピュータの特殊なグラフィック能力を利用するプロ
グラムは、簡単にはこれらの能力を持たないマシン上で
ラン（作業）するように再コンパイルすることはできな
い。（本明細書では、用語「コンピュータ」及び「マシ
ン」が相互に入れ替えて使用される。）上記考察はパー
ソナル・コンピュータの開発で重要性を増して来ている
。多《の種類のハードウエア装置が市場に導入されてお
り、コンパイラ技術の上記制限の為に、ワード・プロセ
ッサやグラフィック向きパッケージのような複雑なプロ
グラムをあるハードウェア装置から他のハードウェア装
置へ移入することは高価である。このことが、市場への
新しいハードウェアの導入に比較し、プログラムの開発
に遅れを来している。すなわち、ソフトウェア開発者は
そのハードウエアの充分な販売かその移入努力に妥当な
見返りの見込みが明らかになるまでその移入を行おうと
するリソース（資源）に関わるのをためらって来た。同
じ理由によって、コンピュータの供給者は、第三者であ
るソフトウエア開発者が彼等のソフトウェアをその新し
いハードウェア基盤へ移入するのに関わるのを待って、
彼等が自己のハードウエアを市場ヘ供給（実捕捉）して
利益を上げることができる。

この状況に応じて、ある供給者は、最初のコンピュータ
即ち「ソース」コンピュータ上で実行するように設計さ
れたソフトウェアの非移入バージョンが、別の「目標］
コンピュータ上で実行するように為されていることに基
づいてスキーマを開発してきた。このようなスキーマは
、いわゆるハドウェア及びソフトウェアのエミュレーシ
ョンを含む。

特にハードウエア・エミュレーションは、例えば、ソー
スコンピュータの機能性をハードウエアに複製するコー
プロセッサの導入を含む。このアプローチの利点はソー
スマシンのものと類似する性能及び開発された大概のア
プリケーションを実行する能力を含む。しかしながら、
ソースマシンの必要な機能性を実効のある費用で正確に
複製することは極めて困難である。実際、ソースマシン
と目標マシンとの間の体系的な相違（例えば、バス体系
の相違）の為に、しばしば、ソースマシンに使用された
ある非標準の周辺装置（例えば、グラフィック・コント
ローラ）は、目標マシン中で支援されず、そのためその
ような周辺装置が存在することに依拠しているプログラ
ムの目標マシン上での実行が排除される場合がある。こ
のようなハードウェア・エミュレーションのアプローチ
では、それらは市場でほんの限られた成功しか得られな
かった。

他のアプローチ、即ちソフトウエア・エミュレションは
、いわゆるエミュレーション・ソフトウェアの使用を意
味し、このエミュレーション・ソフトウエアは実時間で
の入力として、ソースマシンに対してコンパイルされた
目的コード・プロダラムを取り、それが実行されるのに
必要な各インストラクション（命令）を識別し、元のイ
ンストラクションの機能性を複製する一続きの目標マシ
ン・インストラクションを実行することによって、目標
マシン上で同等な演算を実行する。これは、目標マシン
・インストラクションをソースマシン・インストラクシ
ョンに翻訳する効力を持つている。ソースマシン・イン
ストラクションがオベレーティング◆システム又はソー
スマシンの他の特有マシン・サービスを呼び出したよう
な場合には、エミュレーション・ソフトウェアは更に、
そのような呼び出しの各々が起きるのを認識し、対応す
る目標マシン・サービスをアクセスするソフトウェアを
含まなければならない。

ソフトウェア・エミュレーション・アプローチの利点の
一つは、それが実際上比較的安価であることである。更
に、エミュレーション・ソフトウエアは、二つのこと、
即ち＋ａ）ソースマシンと目標マシンの一方又は双方に
生じた変化、ｂ）エミュレーション・ソフトウエア自身
に必要な訂正、例えば、「バグ（虫）」の補修、の二つ
に適応するように容易に修正できる。一方、ソース・ハ
ドウェア上で実行するソースプログラムのものと類似な
性能で、エミュレーションが目標マシン上で実行するて
めに、目標マシン・ハードウエアは、以下に述べるよう
なソースマシン・ハードウェアのものより実質的に優れ
た性能を用意しなければならない。ソースマシンの能力
に従って、この規準は妥当な費用で達成することができ
る。　ソフトウェア・エミュレーションが目標マシンに
優れた性能を必要とする理由には少なくとも二つ有り、
この二つはソフトウェア・エミュレーションが実時間的
性格のものであるせいである。その節一は、エミュレー
トしている目標マシン・インストラクションの実際の実
行に加えて、入力ストリームに応対している各ソースマ
シン・インストラクションを先ず変換するのに時間がか
かるという事実に関係している。第二の理由は、一組の
ソース・プロセッサ・インストラクションの主効力及び
副効力の双方を複製する必要があることに関係している
。

あるインストラクションの主効力は、その表現が意味す
るように、そのインストラクションの基本的な目的であ
る。（例えば、ＡＤＤ　（加算）インストラクションの
主効力は二つの量を加算することにあり、ＪＵＭＰ（飛
び越し）インストラクションの主効力は制御のフローを
変えることにある）。対照的に、副効力は、実行してい
るプログラムにより更に参照するために、ハードウエア
によって保持されているインストラクションの実行から
得られる数片の情報である。（ここで使用されているよ
うな表現「副効力」は、以下により厳密に定義される）
。例えば、副効力は条件コード・レジスタを設定するこ
とを含む。エミュレーション中ソフトウエアがインスト
ラクション毎の原理で動作する限り、そしてその結果、
そのような副効力が極めて希にその実行中に後で参照さ
れようなときは決定できない限り、全ての副効力は目標
マシン中で複写されなければならない。ソースマシン中
でこれらの副効力は、インストラクション自体の肝要な
部分としてプロセッサ・ハードウエアによって実行され
るので、それらはソースマシン中の性能にひどく影響す
ることはない。しかしながら、ソースマシン及び目標マ
シンで使用されているプロセッサでの相違は、典型的に
は目標マシン上でのソフトウェア・エミュレーションの
個々のインストラクションの実行が、ソースマシン上で
実行されているソースインストラクションのものとは完
全に違っている副効力になるかもしれないことである。

従って、目標マシン上に同等な副効力を持たない各ソー
スマシンの各副効力が別の目標マシン・インストラクシ
ョン又はインストラクション列を介して目標マシン上で
はっきりとエミュレートされなければならない。この結
果、プログラム・コードは大量に拡大してしまう。

上記の結果、単にソースマシン上で実行されるプログラ
ムのものと類似な性能を用意するために、ソースマシン
が一つのインストラクションを実行する時間に、目標マ
シンは大量のインストラクションを実行できる能力がな
ければならない。これは、もしソースマシンが旧く技術
が劣ったものであれば、そしてこの場合に実質的に優れ
た性能を持つ目標マシンが妥当な費用で旨く利用できる
なら、たやすく達成できるであろう。しかしながら、不
都合にも、もしソースマシン及び目標マシンの双方とも
似た技術のものであると、使用者は実質的に劣った性能
を容認するか、又は機能は優れているが疑いなく費用が
嵩む目標マシンに投資しなければならない。

他のマシン向けに開発されたソフトウエアを目標マシン
上で実行する第三のアプローチは、「翻訳」と呼ばれる
、上記で略述したようなハードウエア及びソフトウェア
・エミュレーションの双方の欠点のうち少なくともその
幾らかを克服するアプローチである。

翻訳はソフトウェアφエミュレーションに似ていて、そ
れは、典型的には、ソースマシン向けにコンパイルされ
た目的コード・プログラムをその入力として取り、ソー
スマシン・インストラクションを、一組のソース・プロ
セッサ・インストラクションの主効力及び副効力の双方
を複製する一つ以上の目標マシンの目的コード・インス
トラクションに翻訳するソフトウェアを使用することを
意味する。しかしながら、ソフトウエア・エミュレーシ
ョンのアプローチは、実時間でソースマシン・インスト
ラクションを処理することを意味し、即ち、それらはプ
ログラム入力ストリーム中で応対されるが、翻訳はこれ
を「オフライン」で行い、その結果得られた目標マシン
・インストラクションを後での実行のために保存する。

このアブロチの利点は、ソースマシン・インストラクシ
ョンの翻訳を実行時間に遂行する必要性によって引き起
こされる性能の損失が回避されることである。

しかしながら、不都合にも、この翻訳は典型的に、上記
したように、プログラム・コードの前記拡大のせいで大
量の保存スペースを必要とする。更に、この翻訳は依然
として副効力をエミュレートしなければならないので、
これはソフトウエア・エミュレーションと同じく性能低
下の悩みを持つ可能性がある。

（発明の概要） 前述の考察等は、翻訳を基本的に未だ使用されていない
工夫たらしめている。しかしながら、本発明によれば、
劇的に改善された性能を持ち、且つ規模を縮減された翻
訳が、拡張されたプログラム・コードを解析し、且つ、
実際には必要の無いインストラクションを消去すること
によって達成できることが認められた。「不必要」イン
ストラクションは、その消去でプログラムの機能性、即
ち、例えば、計算結果、スクリーン表示、出力ファイル
等の、使用者に対して出現するプログラムの入力／出力
特性が影響を受けないインストラクションである。本発
明によれば、更に、これまでコンパイラ技術で開発され
使用されてきた、いわゆるデータ・フロー解析技術が、
不必要インストラクションの解析及び消去を行うために
、翻訳の問題に旨く適用できることが実感された。

特に、好適な実施例では、解析及びインストラクション
消去が全般的に遂行される。即ち、特定インストラクシ
ョンを保留又は消去する必要性又は不必要性は、翻訳さ
れるプログラムの全体（反対には、例えば、基本フロー
・ブロック又は手順）の検査を基にして決定される。こ
のアプローチは、実際上不必要であると識別できるプロ
グラム・コドの量を最大にする。（事実、このことは、
拡張されたコードの量が膨大であり、その量を減らす各
機会を旨く利用するので重要である。）好都合にも、定
義使用連鎖及び無駄コード消去のコンバイラ用に開発さ
れた技術がこの目的に使用できる。

実際に興味のある多くのプログラムに対しては、単一の
ユニットとして全プログラムを取り扱う全般的なデータ
・フローを実行するのは実際的ではない。制御フローは
、典型的に、単一のユニットとしてプログラムを取り扱
うことが実際見地から満足出来得ない時間及び費用的な
余裕が必要なことに帰着するほど、複雑である。いかし
ながら、本発明のその上の特徴によれば、この潜在的な
障害は手順毎のベース（「手順」の概念は後で充分説明
される）で解析を遂行することによって回避される。こ
の解析を全般的見地から遂行するために、この解析は更
に手順間の関係を考慮する。後者は、例示的には、その
プログラムに亘る多数のデータ・フロー・バスを実行す
ることによって得られる。各パスに於いては、個々の手
順を処理する順序は、手順間の呼び出し関係を定めてい
る、いわゆる呼び出しツリー（ｔｒｅｅ）によって支配
される。

拡張されたコードのそれらインストラクションを保持す
るために必要なことは、事実、その翻訳が従前通り実質
的に元の目的コードより多い保存場所を必要とし、且つ
幾つかの性能上の不利を伴って実行する手段であること
も又注目できる。しかしながら、本発明の更に別の特徴
によれば、いわゆるパターン認識及びその他の最適化技
術が翻訳を、規模に関して元の目的コードに厳密に近づ
《ことができるレベルへ縮小するために使用することが
でき、且つ、性能に於いても多分、同等な他の全ての関
連したパラメータに勝っている。

（以下余白） （実施例の説明） エミュレション及び翻訳の概説 ソースコンピュータ 第１図のコンピュータ１００はパーソナル・コンピュー
タであり、その要部はアドレス、データ及び一般的にバ
ス１２１として示された制御バスを有するプロセッサ１
１１である。バス１２１には、幾つかの周辺装置が接続
される。この周辺装置には、その内容がビデオ・コント
ローラ１１３でＣＲＴ１１４向けにビデオ信号を発生す
るために使用される表示メモリ１１２；プロセッサ１１
１間で直列インタフェースとして働き、他方では、符号
１１６で総合的に示されるキーボード及びマウスとして
働く、汎用非同期レシーバ・トランスミッタ（ＵＡＲＴ
）１　１５　；ハードウェアの割り込みリード（図示せ
ず）が、中でもＵＡＲＴ１１５からそこへ延長される割
り込みコントロラ１１７、プロセッサ１１１とフロッピ
ー・ディスク・メモリ１２９との間のインタフェースと
して働くフロッピー・ディスク・コントローラ１２８：
プロセッサ１１１とハード・ディスク・メモリ１３３と
の間のインタフェースとして働くハド・ディスク・コン
トローラ１３１；プログラムの実行によって作成され、
且つ又は使用されるのみならず、一般に実行のために使
用できるプログラム（以下に述べるオペレティング・シ
ステムを含む）のコピーを保持するランダム・アクセス
・メモリ（ＲＡＭ）１３４　；及びリード・オンリー・
メモリ（ＲＯＭ）１３５を含む。

１００は、そのいわゆるシステム・ソフトウェアの制御
の下で動作する。このシステム・ソフトウェアはアプリ
ケーションのために種々のサービスを実行し、且つコン
ピュータの全体に亘る機能を管理するものである。こう
して、例えば、このシステム・ソフトウェアは、ファイ
ルおよびメモリの管理サービス；表示装置、キーボード
及びマウスの入力／出力（Ｉ／Ｏ）機能；ポートの直列
管理等を提供する。

コンピュータ１００のシステム・ソフトウエアは例示的
には、二つの要素、即ち、基本人力／出カシステム（Ｂ
ＩＯＳ）及びオペレティング・システムとを有する。

コンピュータのＢＩＯＳは、不揮発性メモリ、即ち、Ｒ
ＯＭ中に存在し、この理由から、しばしば、ＲＯＭ　　
ＢＩＯＳとして言及される。特に、コンピュータ１００
中でＲＯＭ　　ＢＩＯＳはＲＯＭ１３５中に存在し、１
３５１で示される。ＲＯＭ　　ＢＩＯＳ１３５１は、ハ
ード・ディスク及びフロッピー・ディスク双方への低レ
ベルでのアクセスを提供するだけでなく、上記した表示
装置、キーボード及びマウスの機能のような基本人力／
出力サービスを実行するためのソフトウェア手順を含む
。ＲＯＭ　　ＢＩＯＳ１３５１は更に「ブート・ローダ
」としての手順を含む。この手順は、コンピュータが電
源投入されたときに、いわゆるハードウェア・リセット
機構を介して呼び出される。その基本機能は、マシン機
能の基本チェックを実行し、それからシステム・ソフト
ウェア（オペレティング・システム１３３１）の残りを
、ハド・ディスク１３３からＲＡＭ１Ｂ４へロードする
ことである。こうしてＲＡＭにロードされて、オペレテ
ィング・システムは後続の実行のために使用できるよう
になる。事実、ＲＯＭ　　ＢＩＯＳはブート・ローダの
実行が終了したときに、制御をオペレティング・システ
ムへ回す。オペレテイング・システム１３３１は、シス
テム拳ソフトウェアの残り、従って、上記したようにコ
ンピュタの全体に亘る機能の管理、ファイル及びメモリ
の管理サービスの提供、ポートの直列管理等を行う手順
を含む。

ソフトウェアの実行の見地から、ＢＩＯＳとオペレティ
ング・システムの間、或いはＲＡＭとＲＯＭの間のシス
テム・ソフトウェアを特に分離することは重要ではない
。例えば、幾つかのマシンでは、全システム・ソフトウ
ェアがＲＯＭ中に在り、一方、他のマシンでは、ブート
・ローダのみがＲＯＭ中に記憶される。しかしながら、
システム・ソフトウェアを翻訳する概念を履行すること
は、以下に詳述するように、システム・ソフトウェアが
特定のソースコンピュータに於いてＲＡＭとＲＯＭの間
をたまたま分離する仕方には全く依存しないことは注目
されよう。

アトレス空間 プロセッサ１１１は、バス１２１を介してそのバスのア
ドレス・リードにアドレスを給与し、且つ、同時にアド
レスされている装置に向けられたコマンド及びデータを
、データ・リード及びコントロール・リードに供給する
ことによって、その種々の周辺装置と通じる。事実、ア
クセスされている装置が（ＲＯＭ又はＲＡＭ）のメモリ
位置として物理的に履行すされるか、或いはいわゆるハ
ドウエア装置又は周辺装置例えばディスク・コントロー
ラ・レヂスタとして物理的に履行されるかどうかで、類
似した動作が使用される。特定の装置に関連付けられた
アドレスは、しばしば製造時に固定され、そのようなア
ドレスの全体は、コンピュータの「アドレス空間」とし
て言及される。

第４図は、ソースコンピュータの「アドレス空間」の例
の論理図を提供する。特に、いわゆる割り込みベクトル
（ＲＡＭに記憶されている）は、記憶位置０で始まるア
ドレス空間に置かれ、幾つかの割り込み制御装置レヂス
タは（１６進）記憶位置Ｏｘ０００４００で始まるアド
レス空間に置かれ、幾つかのフロッピー・ディスク制御
装置レヂスタは記憶位置ＯｘＯＯ０４１０で始まるアド
レス空間に置かれ、幾つかのハード・ディスク制御装置
レヂスタは記憶位置ＯｘＯＯ０４２０で始まるアドレス
空間に置かれ、クロック・レヂスタは記憶位置Ｏｘ００
０４３０で始まるアドレス空間に置かれ、ＲＡＭアドレ
スは再び記憶位置ＯＸ０００４３４を占め、ＲＯＭ　　
ＢＩＯＳ及び他のファームウエアは記憶位置Ｏｘ０００
００で始まるアドレス空間に置かれ、そして表示メモリ
は記憶位置Ｏｘｆｆ６０００て始まりＯｘｆｆｆｆｆｆ
で終了するアドレス空間に置かれる。

しばしば、ハードウェア設計で強制される約束により、
アプリケーション・プログラムは、単に、アドレス空間
のＲＡＭに対応する部分をアクセスするものと仮定され
る。アドレス空間の他の部分全ては、システム・ソフト
ウエア、即ちオペレティング・システム及びＲＯＭ　　
ＢＩＯＳによって排他的にアクセスするものと仮定され
る。このように、アドレス空間のそのような他の部分と
の通信を要求するアプリケーションは、そのアプリケシ
ョンのためのアクセスを実行するシステム・ソフトウエ
ア内での特定の手順を呼び出すことでその通信を要求す
るものと仮定される。システム・ソフトウエアを迂回す
ることにより性能を改善するため、これらの約束を無視
するアプリケーションは、以下で更に詳論するように［
浮浪者（ｒｏｇｕｅ）Ｊと称される。

この点で、最初のソースマシンに対して第二の目標マシ
ン上にコンパイルされたプログラムを実行するための、
ハードウェア・エミュレーション、ソフトウエア・エミ
ュレーション及び翻訳に対する従来技術のアプローチを
幾らか詳しく検討することは有益であろう。

一般に、コンピュータは、タイプが異なる毎に異なるア
ドレス空間レイアウトを持っている。このことは、又、
第４図に示されている。即ち、第４図は、更に、ソース
コンピュータのためにコンパイルされたアプリケーショ
ンが（ハードウェア・エミュレーション或いはソフトウ
ェア・エミュレーションの何れかを用いて）エミュレー
ト或いは翻訳する目標マシンのアドレス空間の説明図を
示す。

ソースマシン及び目標マシンのアドレス空間レイアウト
は、典型的によく有るように、異なることに注意を要す
る。特に、目標マシンの（ＲＡＭに記憶された）割り込
みベクトルは記憶位置０て始まるアドレス空間に置かれ
、幾つかのハード・ディスク制御装置レヂスタは記憶位
置Ｏｘｌ００００で始まるアドレス空間に置かれ、幾つ
かのフロッピー・ディスク制御装置レヂスタは記憶位置
Ｏｘｌ０２０で始まるアドレス空間に置かれ、幾つかの
割り込みベクトルは記憶位置Ｏｘｌ０４０で始まるアド
レス空間に置かれ、表示メモリは記憶位置Ｏｘｌ０６０
で始まるアドレス空間に置かれ、クロック・レヂスタは
記憶位置Ｏｘ６０００で始まるアドレス空間に置かれ、
ＲＡＭアドレスは記憶位置Ｏｘ６００４で始まるアドレ
ス空間に置かれ、ＲＯＭ　　ＢＩＯＳ及び他のファーム
ウェアは記憶位置Ｏｘｆ０００００で始まりＯｘｆｆｆ
ｆｆｆで終了するアドレス空間に置かれる。

ソースマシンと目標マシンのアドレス空間の間には、更
に他のタイプの差異が有ってもよい。例えば、あるマシ
ンは、メモリをアクセスするためと入力／出力（　Ｉ　
／Ｏ）装置をアクセスするためとで分離されたアドレス
空間を持つことができる。

これらは、実際には全てのものを含んでいる単一の（但
し、大きな）アドレス空間を持つものと同じである。従
って、続いて為される論考では、アドレス空間の語は常
にＩ／Ｏのみならずメモリを包含するものとして考慮し
、且つアドレスはメモリの記憶位置又はＩ／Ｏ装置レヂ
スタの何れかに言及することができる。

ソースマシンと目標マシンとのアドレス空間の相違は、
ソースマシンのアドレス空間の全体を、第４図に示すよ
うに、記憶位置Ｑｘｃ０００及びＯｘｌＯＯｂｆｆｆの
間の、目標マシンのアドレス空間のＲＡＭ部へ写像する
ことによる（ハードウェア又はソフトウェアの）エミュ
レーション及び翻訳に於いて説明される。こうして、実
際のソースマシンのアドレス空間の記憶位置及びその目
標マシンのアドレス空間内のいわゆる「イメージ」間に
一対一の対応が有る。従って、種々のエミュレート又は
翻訳されたプログラム・インストラクションに含まれる
アドレスにオフセットを加えることはエミュレーション
又は翻訳ソフトウエアに対して簡単な事項であり、その
結果、それらはソースマシンのアドレス空間のイメージ
内の適切な記憶位置に関係する。こうして、例えば、ソ
ースマシンφインストラクションに現れるアドレス０は
、対応するエミュレート又は翻訳された、対応するイン
ストラクション中のアドレスＯｘｃＯ００に変換される
等するであろう。そのアプリケションが「浮浪者」でな
い限り、その正しい機能はこのアプローチによって維持
される、何故なら、アドレス空間の記憶位置へ非「浮浪
者」プログラムが参照するのは常にＲＡＭへの参照であ
る。ＲＡＭの記憶位置は他のものと区別できないから、
ソフトウェアのエミュレーション又は翻訳を実行するこ
とによりＲＡＭ中の特定な記憶位置にアクセスすること
は、事実、旨くいくであろう。他方、一般にソースマシ
ンのアドレス空間の種々の非ＲＡＭ部分と目標マシン中
のそれらのイメージとの間の対応性は、上記で触れたよ
うに、個々のアドレス空間のレイアウトが殆ど常に相違
しているために失われる。例えば、第４図に於いて、ソ
ースマシンの、装置レヂスタのアドレスは目標マシン中
の割り込みベクトルのアドレスである。従って、もしソ
ースマシンに対してコンパイルされたアプリケーション
が、直接ソースマシンの装置レヂスタの記憶位置を読み
出す（即ち、そのアプリケーションは「浮浪者」である
）と、この読み出しは、メモリ動作の見地から、旨くい
くが、しかし勿論不正確が読み出されてしまう。

理屈では、ソースマシンのアプリケーション・プログラ
ム・インストラクション中に現れる種々の非ＲＡＭのソ
ースマシン・アドレスは認識されて目標マシンのアドレ
ス空間中の対応するアドレスに写像される。しかしなが
ら、コンピュータ自体に存在する相違、例えば、異なっ
た製造者が所与の総称的タイプを持つ周辺装置、例えば
ハード・ディスク制御装置を実現するように規制してい
る約束に相違が存在することは、殆ど常に、そのような
写像が不可能であることを意味している。

従って、エミュレーション及び翻訳への公知なアプロー
チは、簡単には効果的に「浮浪者」プログラムを取り扱
うことはできない。

「浮浪者」プログラムに関する上記考察は又、ソースマ
シンのシステム呼び出しを履行する手順に当てはまる。

何故なら、これらの手順は、必然的にソースマシンのア
ドレス空間の正規でないＲＡＭ領域を引用しなければな
らない。更に、目標マシン中のシステム・ソフトウェア
は、ソースマシンのシステム・ソフトウェアよりは異な
ったサービスを提供し、或いはそれらに異なった約束を
提供することができる。エミュレーション及び翻訳への
公知なアプローチは、ソースマシンのアプリケーション
・プログラム・インストラクションに於けるシステム呼
び出しを認識し、且つ注文で書かれたソフトウエアを使
用することによって、このことを取り扱う。このソフト
ウエアは、ここでは「システム・シミュレーション」と
称され、直接又は目標マシンのシステム・ソフトウェア
への呼び出しを介して、目標マシンのアドレス空間をア
クセスすることによって同等なサービスを提供する。勿
論、後者は目標マシンのアドレス空間のレイアウトを熟
知して書き込まれる。アドレス空間のレイアウトとシス
テム・ソフトウェア双方に於ける上記した相違点はそれ
によって調整される。この点で又、ソースマンン又は目
標マシンのＲＡＭ及びＲＡＭ記憶位置に関するここでの
全論考は、必ずしもディスクリートな物理的メモリへの
言及としては理解されるべきでないことが、又注目され
る。従って、ここでの全論考は、仮想メモリ技術を使用
していないソースコンピュータ及び目標コンピュータ・
システムのみならず、それを使用しているものにも適用
される。

エミュレーション さて、第５図を参照して前述のものを構成する。

第５図は、従来の技術で知られているハードウェア・エ
ミュレーション及びソフトウェア・エミュレーションへ
のアプローチの論理図である。特に、ソースマシン・ア
プリケーション５１が、目標マシン内で実行するハード
ウエア又はソフトウエア・エミュレータ５３への入力と
して使用される。

最初に、エミュレータは、目標マシンのシステム・ソフ
トウェア５８から目標マシンのアドレス空間５５内の適
当な量のメモリを要求することによって、ソースマシン
のアドレス空間のイメージ５４を作成する。それから、
エミュレータ５３は、ａ）アプリケーション５１のプロ
グラム・インストラクションを（以下に説明するように
）デコードし；ｂ）もし、デコードされたインストラク
ションがシステム呼び出しでなければ、そのインストラ
クションを目標マシンの一組のインストラクションの同
等な一続きの動作上に（同じく以下に説明するように）
写像し；そしてＣ）その結果である写像された一続きの
インストラクションを実行する。

デコーディングは、特にコンパイルされたソースマシン
のアプリケーションを個々の要素インストラクションに
分離する動作である。各要素インストラクションは、典
型的には遂行すべき動作を示し、一つ以上の演算数、例
えば、データが常駐して演算されるレヂスタのアドレス
に続く。そして、デコーディングは、処理中、遂行すべ
き動作及び演算が為されるデータを識別する。写像は、
各ソースマシン・インストラクションに対し、副効力を
含み、目標マシンの一組のインストラクションを使用し
ている、目標マシン中の同等な一続きの動作を決定する
動作である。写像プロセスの一部として、エミュレー夕
は以前述べたオフセットを、上記したように種々のイン
ストラクションに含まれるアドレスに加算する。その結
果、ソフトウエア・エミュレーション中のインストラク
ションは目標マシンのＲＡＭ中の適当な記憶位置を引用
する。その結果である写像された一続きのインストラク
ションは、続いて前述した実行ステップ中に目標マシン
中で実行される。

特定のインストラクションをデコードする際に、もしエ
ミュレータ５３が、それがシステム呼び出しであること
を決定すると、それは上記したような写像を遂行しない
。むしろ、それは制御をソースマンンのシステム・ソフ
トウエアの前述したシミュレーション、即ちシステム・
シミュレーション５７へ回す。システム・シミュレーシ
ョン５７は、目標マシンのアドレス空間を直接又は目標
マシンのシステム・ソフトウェア５８を介してアクセス
することにより、要求されたサービスを遂行する。

最終的には、上記し且つ第５図に破線で示すように、「
浮浪者」プログラムにより、イメージのＲＡＭ部外にあ
るソースマシンのアドレス空間中の記憶位置をアクセス
する試みは、一般に、希望の機能か遂行される結果に成
らないであろう。

（一方でのエミュレータ５３、システム・シミュレーシ
ョン５７及び目標マシンのシステム・ソフトウェア５８
と、他方での目標マシンのアドレス空間５５との間の干
渉を叙述する目的で、前者は後者の外部に有る如く論理
図で示される。実際に、目標マシン上で実行する全ソフ
トウェアは、目標マシンのアドレス空間内に、実行され
るために存在しなければならない。このアプローチは同
様に第７図及び第８図にも引き継がれる。）この点で、
ハードウエア・エミュレーション及びソフトウエア・エ
ミュレーションは同様に動作するものと想定される。実
際、それらは第５図に表された機能レベルでそうなって
いる。基本的な相違は、ソフトウエア・エミュレーショ
ンに於いては、目標コンピュータのプロセッサが上記動
作の全てを実行するのに依存しており、ハードウエア・
エミュレーションに於いては、目標マシンが、タイプが
ソースマシンのそれと同等な第二のプロセッサを含み、
ソースマシンのアプリケーション・プログラム・コード
が直接この第二プロセッサ上で実行されることである。

このアプローチは、前述したデコーディング・ステップ
が全く必要とされず、写像ステップが前述したオフセッ
トの加算を実行する限りでのみ必要となる、確かな効力
を奏する。こうして、ハードウエア・エミュレーション
の性能は、一般にソフトウエア・エミュレションのそれ
より（典型的には、１００倍）良くなる。他方、ソース
マシンのシステム環境と目標マシンのそれとは違ってい
るので、ハードウエア・エミュレーションは、依然とし
て上記したようにシステムφシミュレーションを介して
システム・サービスを遂行するために、目標マシンのプ
ロセッサに依存しなければならない。ハードウエア・エ
ミュレーションの基本的な欠点は、特定のソースマシン
をエミュレートするために必要とされるハードウエアが
、目標マシンの費用を酷く高価にすることである。実際
、各ソースマシンをエミュレートするために、異なった
ハードウエア・エミュレータが目標マシンに必要とされ
る。こうして、例えば、三台のソースマシンからソフト
ウェアを動かすには、四個のプロセッサ、即ち目標マシ
ンのものに加えて各ソースマシン毎に一つ、が必要とさ
れる。

翻訳 都合良く、翻訳はソフトウェア・エミュレーションとハ
ードウエア・エミュレーション双方の幾つかの欠点を克
服する。

翻訳は、それが、ここで「トランスレータ」と称するソ
フトウエアの使用を伴う点で、ソフトウェアーエミュレ
ーションと似ている。このトランスレータは、その入力
として、ソースマシンに対してコンパイルされたプログ
ラムを取り、且つ各ソースマシン・インストラクション
の機能を複製する一つ又はそれ以上の目標マシン・イン
ストラクションに各ソースマシン・インストラクション
をデコードし、写像する。しかしながら、ソフトウエア
・エミュレーションと対比すると、このデコーディング
及び写像は「オフライン」で実行されてその結果のソフ
トウェア翻訳が保全される。

その結果、アプリケーションが目標マシン上で実行され
ようとする度毎に作り直すよりむしろ、それは繰り返し
実行することができる。

第６図は、上記したように、「翻訳」コンピュータに於
いて遂行される翻訳プロセスのオフライン段階を示す。

特に、ソースマシン・アプリケーション６１は、翻訳さ
れたアプリケーション、即ち、より単純には、後での使
用のために記憶される「翻訳」６３を出力するトランス
レータ６２への入力として働く。トランスレータ６２の
最も単純なタイプの実施例では、翻訳６３を有する一続
きの目標マシン・インストラクションは、実際の目的に
対しては、ソフトウエア・エミュレータによって使用さ
れるであろうものと同じである。

翻訳６３の実行時実行が、第７図に示される。

この図で、それは７１として参照される。ここで再び、
少なくとも最も単純な場合に於いては、続きのインスト
ラクションは、実質的に、ソフトウェア・エミュレーシ
ョンの場合に於けるものと同じであるから、実行インス
トラクションと目標マシンの間の相互作用も又、実質的
に同じである。

こうして、特に、翻訳されたアプリケーション７１は目
標マシンのアドレス空間７５内で、ソースマシンのアド
レス空間のイメージ７４をアクセスする。システム呼び
出しは、システム・シミュレーション７７へ渡される。

システム・シミュレション７７は、順次、目標マシンの
アドレス空間７５を直接又は目標マシンのシステム・ソ
フトウエア７８を介してアクセスする。そして、先程と
同じく、「浮浪者」プログラムにより、イメージの通常
ＲＡＭ部の外にあるソースマシンのアドレス空間中の記
憶位置をアクセスする試みは、一般に、希望の機能が遂
行される結果に成らないであろう。

この点で、この説明に於いて、翻訳コンピュタ及び目標
コンピュータを更に詳しく述べることが好適であろう。

特に、第２図は、「翻訳」コンピュータ２００の説明図
を示し、この「翻訳」コンピュータ２００上で、第６図
に示す翻訳プロセスのオフライン段階が例示的に遂行さ
れる。翻訳コンピュータ２００は例示的にはミニコンピ
ュータであり、その全体的アーキテクチャはソースマシ
ン、実際、最３つ 新式コンピュータのそれと同様である。しかしながら、
コンピュータ１００と２００の間には幾つかの相違があ
る。

例えば、翻訳コンピュータ２００は表示メモリや、はた
また分離されたキーボード及びマウスを持っていない。

むしろ、全ての使用者インターフェースは例示のように
、従来のコンピュータ端末２１３に接続された直列ポー
ト・コントローラ２１２を介して遂行される。更に、こ
のシステムはフロッピー・ディスク・メモリを持ってい
ない。

むしろ、ミニコンピュータ環境で典型的であるように、
テープ・コントローラ２２８によって制御される磁気テ
ープ・ドライブ２２９の手段によって、ソフトウェアと
データの双方又は一方が、そこへ入力されたりそこから
出力されたりするコンピュータである。翻訳コンピュー
タ２００の他の全ての要素は、ソースコンピュータ１０
０に対応する要素を持っており、参照符号の後部二桁に
同一数字を持つ。

翻訳コンピュータ２００のオペレティング・システム２
３３１に加えて、第２図は、更に翻訳プロセスに於いて
特に好適な、翻訳コンピュータ２００のハード・ディス
ク・ユニット２３３中のこれらのファイルを示す。特に
、ハード・ディスク・ユニット２３３は、第６図のトラ
ンスレータ６２に相当し、このコンピュータ上で第６図
に示す翻訳プロセスのオフライン段階を実行するアプリ
ケーションとして実行されるトランスレータ２３３２；
第６図のソースアプリケーション６１に相当し、トラン
スレータ２３３２への入力として働く、二つのソースマ
シン・アプリケーション２３３３及び２３３４；そして
最後に、第６図の翻訳されたアプリケーション６３に相
当し、ソースマシン・アプリケーション２３３３及び２
３３４をそれぞれ処理した結果として、トランスレータ
２３３２の出力積を表す、二つの翻訳されたアプリケー
ション２３３５及び２３３６を記憶する。例示的に、ト
ランスレータ２３３２は、コンビュタ２００上ではなく
、むしろ、第三の目標コンピュータ、例えば、第３図に
示すコンピュータ３００で実行するように意図された翻
訳を作成するように設計されており、以下に説明される
。こうして、ソースマシン・アプリケーション２３３３
及び２３３４と翻訳されたアプリケーション２３３５及
び２３３６の何れも翻訳コンピュータ２００上で実行で
きない。むしろ、コンピュータ２００に関する限り、そ
れらは、それぞれ、単に人力及び出力を構成する。

第３図は、目標コンピュータ３００を例示的に示し、そ
の上で第７図で示すような（後で、更に第８図でも示す
ような）翻訳されたアプリケーションが実行される。目
標コンピュータ３００は、例示的には、グラフィックス
・ワークステーションである。目標コンピュータ３００
が、ソースマシン１００上で実行されるものを写し取る
機能を遂行するものである限りでは、この二つのコンピ
ュータは、当然、多くの同様な要素を含み、それらは参
照符号の後部二桁に同一数字を持つ。しがしながら、そ
れらには、先と同様に、幾つかの相違がある。

特に、目標コンピュータ３００は、翻訳コンピュータ２
００と同様、フロッピー・ディスク・ユニットを持たな
い。外界との接続は、ＬＡＮコントローラ３２８による
ローカル・エリア・ネットワーク（ＬＡＮ）の手段によ
って為される。他の基本的な相違は、ＲＯＭ３３５が完
全なＢＩＯＳは含まず、むしろ上記したように、ブート
・ローダ３３５１のみを含むことである。オペレティン
グ・システム３３３１に加えて、第３図は、更に、第７
図で示すような翻訳プロセスの実行時部分に特に好適な
、目標コンピュータのハード・ディスク３３３中のファ
イルを示す。特に、ハード・ディスク３３３は、第２図
の翻訳されたアプリケション２３３５及び２３３６に対
応する、翻訳コンピュータ２００によって出力された二
つの翻訳されたアプリケーション３３３２及び３３３３
、及び第７図の翻訳されたアプリケーション７１を記憶
する。更に、例示的にハード・ディスク３３３上には、
目標コンピュータ３００上での実行のためにコンパイル
された二つのアプリケーション３３３４及び３３３５が
記憶されている。

ハード・ディスク３３３中に示される他のファイルにつ
いては後でもつと折よい時機に考察する。

システム・ソフトウエアの翻訳 第８図は１翻訳構成の代案を示す。以前のように、ソー
スマシンからの翻訳されたアプリケーション・プログラ
ム８１はソースマシンのアドレス空間のイメージ８４を
アクセスする。しかしながら、ここでは、シミュレーシ
ョンである代わりに、翻訳されたアプリケーションとし
て働くシステム・ソフトウェアは、少なくとも部分的に
、ソースマシンのシステムφソフトウエアの少なくとも
数部分の翻訳８７である。実際、ソースマシンのシステ
ム・ソフトウエアのこの翻訳は、このソースマシンのシ
ステム・ソフトウエアを全く同じアプリケーション処理
、即ち第６図に示すような処理に当てることによって作
成される。

ソースマシン・システム・ソフトウェアの全体を翻訳す
る必要が無いことは、強調されるべきことである。例え
ば、もし、特定のシステム・サービスが、実質的にソー
スマシンと目標マシンの双方に同様に設けられていれば
、翻訳されたアプリケーションを目標マシン・バージョ
ンにつなぐために、そのサービスのソースマシン・バー
ジョンを履行するコードの翻訳を更に進めることができ
る。翻訳されたシステム・ソフトウェア８７は又、目標
マシンのシステム・ソフトウェア８８を、現にシステム
・シミュレーションが行っているのと大部分同じ仕方で
呼び出すことができる。他の場合では、ソースマシンの
システム・ソフトウエアの一部を翻訳するより、むしろ
シミュレートし、且つ再びそれらに翻訳されたアプリケ
ーションをつなぐことが有益であると考えられる。更に
、アプリケーションによりアクセスされることが期待さ
れていないソースマシン・システム・ソフトウエアの要
素は翻訳される必要が無い。

翻訳されたシステム・ソフトウエア８７は目標マシン３
００（第３図）にライブラリとして記憶され、そこでは
参照数字３３３６を持つ。第２３図を参照して後で更に
詳述するように、翻訳されたアプリケーションは、それ
らが実行のため目標マシン３００のＲＡＭ３３４にロー
ドされる前に、翻訳されたシステム・ソフトウエアに結
合される。

こうして、翻訳されたアプリケーション８１が少なくと
も、特定のシステム・サービスを要求するとき、単なる
シミュレーションよりむしろ、目標マシン上で実行され
るこれらのサービスを履行するソースマシン・システム
・ソフトウエア・プログラムの翻訳されたバージョン、
即ちそれの機能的に書かれたバージョンである。

翻訳されたシステム・ソフトウエア８７は、それがソー
スマシン中で行っていたように、ソースマシンのアドレ
ス空間のイメージ上で正確に動作する。ソースマシン・
システム・ソフトウエアのセマンティックス（意味）は
、こうして同一に保全される。このことは、シミュレー
ションの伝統的技術のアプローチ、即ちソースマシン・
システム・ソフトウエアの書き直しを越えた顕著な利益
を持っている。

特に、システム・ソフトウエアの開発者により提供され
た、実際に特定のシステム・サービスをソフトウェア中
で遂行する方法の記述は、しばしば、ａ）一つ以上（大
概は少ない）の事柄で不正確であるか、ｂ）不完全であ
るか、又はその双方である。その結果、そのような記述
を元にして書かれたマシン・システム・ソフトウェア・
シミュレーションは、これらは通常利用できる唯一のソ
ースであるが、オリジナルに存在している特定の機能を
具体化することは出来ない。シミュレートされたシステ
ム・サービスを呼び出すエミュレトされたアプリケーシ
ョン又は翻訳されたアプリケーションは、こうして適切
に実行出来ない。対照的に、ソースマシンのシステム・
ソフトウエアは、実際、浮浪者プログラムの作成者が時
折その利益を得るプログラム・バグ（プログラムの虫）
を含めて、それらのニューアンスの全てが保全されるの
を確実にする。

翻訳されたシステム・ソフトウエア８７によって参照さ
れるすべてのアドレスはイメージ８４内にある。即ち、
それらはソースマシン内のメモリ記憶位置及び装置のア
ドレスである。浮浪者プログラムに関する上記考察は、
こうして翻訳されたシステム・ソフトウエア８７に適用
される。特に、ソースマシン及び目標マシンのアドレス
空間が、必す相違しているという事実は、参照されるア
ドレスが両方のマシン内に於ける記憶位置、装置非関連
の、即ち通常ＲＡＭに対応している限りでは、通常ＲＡ
Ｍの記憶位置は互いに見分けがつかないものであるから
、問題では無い。しかしながら、二つのアドレス空間の
相違が調和されない限り、たとえば、特定のハードウェ
ア装置に関連付けられた記憶位置へ試みられたアクセス
は、一般に適切には遂行されない。

都合よく、仮想ハードウェア環境が、前記のものを扱う
ために目標マシンに備えられる。特に、翻訳ソフトウエ
アの要素、例えば、仮想ハードウエア事象モニタ８９は
、周期的に、例えば０．０１秒毎にタイマー割り込みに
応じて呼び出される。

後で詳述するように、モニタ８９はソースマシンのハー
ドウェア装置に対応するイメージ８４内の記憶位置の全
ての状態をチェックし、もし最終チェックの前に変化が
生じた場合、直接又は目標マシンのシステム・ソフトウ
エア８８を介して目標マシンのアドレス空間に意図され
たアクセスを遂行する。更に又、モニタ８９は、目標マ
シンのハードウェアに対応する目標マシンのアドレス空
間のそれらの記憶位置をモニタし、イメージ８４内の対
応する記憶位置を更新する。その結果、目標マシンのハ
ードウェアの状態の変化は、翻訳されたアプリケーショ
ン８１及び翻訳されたシステム・ソフトウェア８７に知
得される。

アプリケーションがソースマシン内で働《のと同様な仕
方で翻訳されたアプリケーション８１を満足する、翻訳
されたシステム・ソフトウエア８７の能力は、目標マシ
ンのシステム・ソフトウエア８８に関連して、ソースマ
シンのハードウエアの動作を正確にシミュレートするた
めの項目モニター８９の設計者の能力に依存する。有益
なことに、典型的にソースマシンのシステム・ソフトウ
ェアに使用できるドキュメンテーションの不適切性に関
して上記で概説した問題は、そのハードウエアをシミュ
レートする状況に於いては生じない。

その理由は、種々のハードウェア素子に対するインター
フェースが旨く規定されており、実際、項目モニター８
９の設計者に使用出来るドキュメンテーションがソース
マシンのハードウエア設計者によって使用し得、且つ依
存されるものと同じであり、このドキュメンテーション
が種々のハードウェア要素の種々の製造者によって供給
されるものであるからである。こうして、目標マシンの
システム・ソフトウェア８８に関連して、項目モニター
８９の設計者がソースマシンのハードウエア装置の特徴
や性質を充分に履行する限り、翻訳されたアプリケーシ
ョン８１及び翻訳されたシステム・ソフトウェア８７に
より呼び出されるように企画されたハードウエア機能は
、事実、同様に実行することが出来る。

第９図は、仮想ハードウェア項目モニター８９の動作の
フローチャートである。特に、モニタ８９は、ステップ
９０２で、モニタの最後の呼び出し後に、翻訳された（
アプリケーション又はシステム）ソフトウエアを実行す
ることがスクリーン変化を為したかどうかを決定するこ
とによって、即ち、イメージ８４内のスクリーン・メモ
リに書き込むことによって、開始する。この検査は、目
標マシンの能力に応じて、幾つかの方法で遂行される。

もし、変化が有った場合、モニター８９は、目標マシン
の実際のスクリーン・メモリ内で、変化した画素の値を
更新するために、目標マシンのシステム・ソフトウエア
８８を呼び出す。

モニター８９は、それからステップ９１４へ進む。ここ
で、それは目標マシンのクロック・レヂスタに記憶され
た現在の値を仮想クロック・レヂスタ、即ち目標マシン
のクロック・レヂスタに対応するイメージ８４内の記憶
位置にコピーする。

同様に、ステップ９１６で、マウス座標がイメジ８４内
の類似した記憶位置に記憶された、目標マシン内の記憶
位置に記憶された現在の値をコピーする。

最後に、キーボードがステップ９１７に於いて検討され
る。特に、モニター８９は、キーボードの項目が置かれ
ている目標マシンのシステム・ソフトウェアによって維
持された待ち行列をチェックする。もし、この待ち行列
が最後にチェックされた後で変化が有ったことが判ると
、処理はステップ９２３へ進み、ここでこの情報は翻訳
されたアプリケーションを実行することによって知得さ
れる。例示するように、これは単にキーボードの項目情
報を直接、イメージ８４内に維持されている類似した待
ち行列中に置くことによって達成される。また別に、翻
訳されたソースマシンのシステム・ソフトウェア内の割
り込み手順は、その情報をその待ち行列中に置くように
、モニター８９によって呼び出すことも出来よう。

この点で、モニター８９は後で再呼び出しされるべく、
出力する。

第１０図は、翻訳ソフトウェアの開発から翻訳されたソ
フトウェアの実行まで、翻訳を遂行するための項目の順
を示すフローチャートである。

１００１及び１００３で示されるように、最初のステッ
プは、トランスレータ及び仮想ハードウェア項目モニタ
ーを作成することである。勿論、これは基本的にコンピ
ュータのプログラミング・タスクである。

一旦、トランスレータ及び仮想ハードウェア項目モニタ
ーが作成されてしまうと、ａ）ソースマシンのシステム
・ソフトウェアの全部又は一部を翻訳し、それを目標マ
シン中に、１００６、１００８及び１０１１で示すよう
に記憶し；ｂ）所望のシステム・シミュレーション・ソ
フトウェアを履行し、それを目標マシン中に、１ｏ１２
及び１０１３で示すように記憶し；及び、Ｃ）一つ又は
それ以上のアプリケーションを翻訳し、それらを翻訳さ
れたシステム・ソフトウェア及び他のシステム・ソフト
ウエアに纏めて、目標マシン中に、１０１４、１０１６
、１０１９、１０２０及び１０２２で示すように記憶す
るステップを遂行することが可能になる。ステップ１０
２４で判定されるように、もし目標マシン上で翻訳され
たアブリケーンヨンの特定の一つを実行することが求め
られると、そのアプリケーションは、１０２８で示すよ
うに直接実行される。

特に、ステップ１０２８は、目標マシンのシステム・ソ
フトウエア８８内のアプリケーション始動手順によって
例示的に遂行される。この手順はイメージ８４に対しメ
モリ空間を割り付ける目標マシンのシステム・サービス
を呼び出し；基本的にそれが前述したタイマ割り込みを
設定するように指示することによって、翻訳されたアプ
リケーション８１をそのイメージ内の適当な場所にロー
ドしてモニター８９を始動し；且っそれから制御をアプ
リケーション８１へ渡す機能を勤める。アプリケーショ
ン８１の実行が完了したとき、アプリケーション始動手
順は、それにそのタイマ割り込みを停止するよう指示す
ることによってモニター８９を停止し；イメージ８４に
割り付けられたメモリ空間を解放し；且つ、プログラム
制御を目標マシンのシステム・ソフトウエア８８へ戻ス
よう、機能する。

トランスレータ ここで、第２図中のトランスレータ２３３２及び第６図
中のトランスレータ６２として示される、実際の翻訳を
行う翻訳ソフトウエアのこの部分を例示的に実現するこ
とについての詳しい論考に移る。

ソフトウェア・エミュレーションを通しての翻訳の基本
的な利益は、さもないとデコーディング及び写像で費や
される時間が排除され、顕著な、典型的には約３対１の
性能改善となる事実である。

しかしながら、不利益にも、翻訳されたソフトウェアは
、一組のソースマシン・インストラクションの主効力及
び副効力を明確に複製する必要性から起きる上記したプ
ログラム・コードの拡大のせいで、典型的には膨大な量
の記憶空間、例えば典型的に元のプログラム・コードの
１５倍乃至２５倍の増加を必要とする。副効力が明確に
複製されるときにソースマシン／コードが拡大する仕方
の例は、第１１図の最初の二カラムに示されている。

プログラム・コードのこの拡大、及びそれに付随して必
要な多量の記憶場所と実行速度の低下は、この点で、目
的コードの翻訳を本来使用されない別の手段に変えてい
た。

しかしながら、本発明によれば、劇的に性能が改善され
且つ規模を縮小された目的コードの翻訳が、拡大したプ
ログラム・コードを解析し、実際には、適当なプログラ
ム実行に対して必要ではないインストラクションを排除
することによって、達成することができる。実際、以下
に述べるように、もし本発明の種々の特徴及び見地に従
ってこのことが遂行されれば、その結果得られる一組の
インストラクションは、ソースマシンのアプリケション
・コードより顕著に多い記憶場所を必要とはしなくなる
。第１１図の第３カラムはこれら最適化技術が生じるこ
とのできる縮減度合を示す。

第１２図は、本発明による翻訳を遂行するためのトラン
スレータによって行われる処理の概観を表す。この翻訳
プロセスは、三つの基本要素、即ち、分析、翻訳及びコ
ード発生を有するように、多くの点で伝統的コンパイラ
・プロセスと類似している。特に、分析要素は入力アプ
リケーション・ソフトウェア又はシステム・ソフトウェ
アの目的コードを読取り、それを更にマシン非依存性の
処理の適する中間言語表現に変換する。ついで、翻訳要
素は冗長度及び不必要コードを排除することにより、中
間言語コードの規模を縮小する。最後に、コード発生要
素はその中間言語表現を目標マシンの目的言語に変換す
る。

これら三要素をこれから順に説明する。

分析 分析要素は三つの段階（フェーズ）、即ち分解、解析及
び写像を持っている。

分解は、目的コードの個々のインストラクションの正直
なデーコーディング及びそれらのアセンブリ言語形態へ
の変換から成り、これらデーコーディング及び変換の双
方は周知の伝統的技術に従って遂行される。引き続いて
、解析フエーズ分解処理の管理に責任を負っている。

分解／解折の初期タスクは、いわゆる基本ブロックに分
けられた入力プログラムのアセンブリ言語表現を作成す
ることである。基本ブロックは、インストラクションの
一順序（シーケンス）であり、これは実行中のそのとき
に正確に制御がそのシーケンスに入ることができるーイ
ンストラクション及び実行中のそのときに正確に制御が
そのシケンスから出ることができるーインストラクショ
ンを有している。解析中、各基本ブロックは、ａ）その
基本ブロックに対し任意に選択された名称、ｂ）その基
本ブロックの開始点、Ｃ）その基本ブロックの終了点、
及びｄ）その基本ブロックのいわゆる「後続」を識別す
るコメント・ラインで注釈される。これらは、制御のフ
ローがそこへ直接渡され得る基本ブロックである。例示
的には、一本のコメント・ラインがａ）とｂ）の双方を
果たすのに仕様される。上記のように注釈され、且つ後
で詳述するようないわゆる「手順」に分類される数個の
基幹的基本ブロックが、第１５図に示される。

基本ブロックを識別するプロセスはいわゆる「セグメン
ト・リスト」を作成することによって遂行され、そのリ
ストは、コード又はデータの何れかであるとして識別さ
れるプログラムのセグメントの開始位置及び終了位置を
含む。初期に、第１４図に１４０５で示されているプロ
グラムの全体は、試験的にデータ・セグメントとして識
別される。こうして、１４図に１４０３で示されている
ように、そのセグメント・リストは、初期には単一の記
述項を含み、この記述項はそれぞれｒＡＪ及びｒＺＪで
示されている完全プログラムの開始位置及び終了位置を
含む。コードの各セクションは解析益として見出だされ
るので、それらは、以前にそれらを含んでおり且つセグ
メント・リスト内で「コード」として更に分類されてい
る、先にデータとして試験的に識別されたセグメントか
ら「引き離し」をされる。一旦、これらの処理が完了す
ると、各コード・セグメントは基本ブロックとして認証
される。

第１３図はトランスレータの分析要素全体のフローチャ
ートであり、そのフローチャートの大部分はコード・セ
グメントとデータ・セグメントの識別に、従って究極的
には基本ブロックの識別に当てられている。実際、第１
３図が充分に記述された後で評価されるが、ステップ１
３１１は分解を遂行し、ステップ１３３５は写像を遂行
し、且つ残りのステップは分析を遂行する。

処理はステップ１３０１から開始し、ここで知得されて
いる基本ブロックの開始点のリストであるいわゆる探求
リストから記述項を取り出す。初期には、この探求リス
トは、目的コード・プログラム、即ちプログラムの実行
が開始するときに制御を受けることができる目的プログ
ラム内の記憶位置に対する入口点のリストである。普通
、アプリケーションは一個の入口点のみを持っている。

しかしながら、更に翻訳することができるシステム・ソ
フトウェアは典型的には多数の入口点、即ちアプリケー
ションがそこでそれを呼び出すかも知れない種々の記憶
位置の全部を有する。初期の探求リストは、第１４図に
１４０１で示されており、この場合は単一の記述項、即
ちｒＥＪで示されているこのプログラムの入口点の記憶
位置を有する。種々の他の基本ブロックの開始点は後で
述ベる方法で識別されるので、それらは探求リストに加
えられる。

ステップ１３０３で判定されるように、もし探求リスト
が空であれば、コード・セグメント・ブロックとデータ
・セグメント・ブロックを識別する処理は完了する。そ
うでない場合は、ステップ１３０７て検討中のアドレス
に於けるインストラクションが実際、既に遭遇済みであ
るか否かを判定するために、更に検査が為される。この
粉とが起きる可能性については、後のもっと折よい時期
に述べる。

実際、もし検討中のインストラクションが以前に遭遇さ
れていなかった場合、それは定義により、新規に識別さ
れた基本ブロックであり、そのアドレスは後で使用する
ために保存される。従って、初期には、それは記憶位置
ｒＥＪで保存される。

ついで、処理はステップ１３１１へ続く。この点で、そ
のインストラクションは分解され、その結果、次のステ
ップ１３１３はそのインストラクションが制御のフロー
を変える稼働か、即ちブランチが呼び出しか戻しである
かを判定することができる。もしそれが制御のフローを
変えないと、そのセグメントの端部が未だ見付けられて
いない。

そのアドレスはステップ１３１５で増分され、且つステ
ップ１３１１及び１３１３が次のインストラクションに
対して繰り返される。

究極的には、制御のフローを変えるインストラクション
が遭遇される。第１４図に１４１５で示されるように、
この例ではそのインストラクションは記憶位置ｒＦＪの
ブランチ・インストラクションである。ステップ１３１
７は、現在のインストラクションが制御を移すことので
きるインストラクションのアドレスを、そのようなアド
レスの各々が定義により各基本ブロックの最初のインス
トラクションであるので、それらを探求リスｌ・へ加え
る。この例では、記憶位置ｒＧＪ及び「Ｋ」が、制御の
フローが記憶位置ｒＦＪでのブランチ・インストラクシ
ョンからそこへ渡ることができるインストラクションで
ある。ついで、ステップ１３１９は、セグメント・リス
トに新しいコード・セグメントの記述項を作成するため
に、ステップ１３０９で保存されたアドレス及び現在の
アドレスを使用する。こうして１４１３で示されるよう
に、そのセグメント・リストは現在、三個の記述項、即
ち、記憶位置「Ａ−ＥＪ及びｒＦ　−　ＺＪの仮りデー
タ・セグメント及び記憶位置ｒＥ−Ｆｊのコード・セグ
メントを含む。ここでは、記憶位置ｒＥ−ＦＪに新しく
作成されたコード・セグメントが基本ブロックであるこ
とを述べるのは、そのセグメント内のインストラクショ
ンが目的の、即ち未だ遭遇していないブランチ・インス
トラクションであり、且つそれでそれがそれ自体の基本
ブロックの最初のインストラクションであることは後で
判明することなので早すぎる。事実、後で分かるように
、記憶位置ｒＫＪはちょうどそのような目的のインスト
ラクションの記憶位置である。

この点で、処理はステップ１３０１へ戻り、探求リスト
から別の記述項、ここでは記述項ｒＧＪを処理する。こ
の場合、同様な処理ステップが続き、その結果、記憶位
置ｒＧ−ＨＪでの別のコード・セグメントの識別及び、
その記憶位置でのインストラクションが記憶位置ｒＨＪ
でのインストラクションの目標である記憶位置ｒＭＪの
探求リストへの付加が為される。

処理は再びステップ１３０１へ戻る。しかしながら、記
憶位置ｒＫＪが記憶位置「Ｅ−Ｆｊでのコード・セグメ
ント内にあることに注意を要する。

こうして、ステップ１３０７での検査の結果は、記憶位
置ｒＫＪが記憶位置ｒＥ−ＦＪてのコード・セグメント
を識別した処理中に遭遇されているので、現在「ＹＥＳ
」である。

ついで、ステップ１３０８は、現在のインストラクショ
ンが既に識別されたセグメントの最初のインストラクシ
ョンであるか否かを判定する。このことは、もし記憶位
置ｒＫＪが既に探求リスト上に置かれていた場合、その
結果が記憶位置ｒＨＪでのインストラクションより以前
に遭遇されたインストラクションの目標であるので、起
こり得る。

その場合、それ以上のことは為される必要は無句、処理
は再びステップ１３０１へ戻る。しかしながら、この場
合、記憶位置ｒＫＪは未だ既に識別されたセグメントの
最初のインストラクションとしては識別されていない。

従って、記憶位置「ＫＦ」での新しいセグメントはステ
ップ１３１０で引き離され、処理は再びステップ１３０
１へ戻る。

究極的に，ステップ１３０３で、探求リストが空である
ことが見出だされよう。この点で処理中にコードとして
識別されなかったセグメント、即ち非インストラクショ
ンは何れも、制御のフロー中のバスで、それによって、
ことによりそのようなインストラクションが実行のため
に到達できるようなものは見出だされていないので、デ
ータである。なおこの点で、使用した方法論によって、
すべてのコード・セグメントは基本ブロックとして保証
される。

処理はここでステップ１３０３からステップ１３３１へ
進み、ここでは基本ブロックの前述した後続要素が識別
される。これは各基本ブロックの最終インストラクショ
ンを単に検査し、且つ制御のフローがそこへパスするこ
とができる基本ブロックを判定することにより達成する
ことができる。

ついで、元プログラムのいわゆる手順はステップ１３３
３で識別される。これは、最初にそれら基本ブロックの
個々の一つがいわゆる「手順先頭ブロック」であるとし
て識別することにより得られる。なお、手順先頭ブロッ
クはその最初のインストラクションが、ａ）前述した入
口点又はｂ）呼び出しインストラクションの目標の何れ
かである基本ブロックである。ある手順は、ａ）それ自
体は手順先頭ブロックではなく、且つｂ）制御のフロー
がどのような中間手順先頭ブロックを介してもそこへは
バスしない、いわゆる手順先頭ブロックから、（後続要
素のシーケンスを介して）到達し得る全てのブロックで
構成される。

第１５図は、１５０１から１５０５までの多数の基本ブ
ロックを示し、ここに、それら基本ブロックの手順への
グループ化が例示的に示されている。ここで、各基本ブ
ロックが、基本ブロックの開始点とその名称を意味する
ｒ＃ＢＬＯｃＫｂ　１ｏｃｋｌ５０ｘＪの形態のコメン
ト・ライン；基本ブロックの終了点と又その名称を意味
する［＃ＥＮＤＢＬＯＣＫｂ　１　ｏｃｋｌ５０ｘＪの
形態のコメント・ライン；基本ブロックの後続要素と勿
論そのプログラム・コードを意味するｒ＃ＳＵＣＣＥＳ
ＳＯＲＳ　　１５０ａ，１５０ｂ，等」の形態のコメン
ト・ラインを有することが注意される。

制御のフローを変更するインストラクションのみが、そ
の図に明確に（プログラム疑似コードで）示されている
。

基本ブロック、即ちｒＡ−１０Ｊの最初のインストラク
ションは入口点である。従ってその基本ブロックは手順
先頭ブロックである。残りの基本ブロックの全部はブロ
ック１５０１から到達する。

特に、基本ブロック１５０２及び１５０３は条件ブラン
チを介してＬＡＢＥＬＩへ到達する。もしそのブランチ
が取られると、制御のフローがＬＡＢＥＬＩヘバスし、
このＬＡＢＥＬＩは基本ブロック１５０３の最初のイン
ストラクションをマクする。そうでない場合は、基本ブ
ロック１５０２の最初のインストラクションに対しその
ブランチを「失敗」に制御する。ブロック１５０４は呼
び出しにより、基本ブロック１５０３からＬＡＢＥＬ２
へ到達する。最後に、基本ブロック１５０５はブロック
１５０４の「失敗」及びそれ自体の双方により、条件ブ
ランチを介してＬＡＢＥＬ３へ到達する。

後続要素１５０２及び１５０３は基本プロ・ソク１５０
１に続く手順である。しかしながら、基本ブロック１５
０４及び１５０５は、なおそれらは又基本ブロック１５
０１のついての後続要素であるが、他の手順に属する。

先ず、基本ブロック１５０４は、それが呼び出しの目標
であるので、自己の権利で手順先頭ブロックとして適任
である。

更に、基本ブロック１５０５から基本プロ・ソク１５０
１への制御のフローは、中間手順先頭プロ・ソク、即ち
基本ブロック１５０４を介してバスする。

それ故、基本ブロック１５０５は基本プロ・ソク１５０
１を先頭とする手順中には無い。むしろ、それは、基本
ブロック１５０４を先頭とする手順中のみに存在する。

第１３図のステップ１３３３は分析要素の解析フエーズ
を完成する。最終の分析ステップ、即ち写像は、ついで
ステップ１３３５で遂行される。

これは、各分解インストラクションに対し、マシン非依
存性の中間言語で表された副効力を含めて動作の等価シ
ーケンスを代行するプロセスである。

こうして、ステップ１３３５で遂行された写像プロセス
は、前述したように、伝統的ソフトウェア・エミュレー
ション中に遂行される写像と全く同じである。

この点で、用語「副効力」の意味と、写像プロセスが、
実際、ソースマシン・インストラクションのセットの副
効力のセマンティックスのすべてを中間言語表現中に複
製するために、管理されねばならない理由をより充分に
述べることが適切である。

限定すれば、インストラクションのセットはコンピュー
タのプログラマーが使用可能な全インストラクションの
全体効力である。各インストラクションは、そのインス
トラクションの形態を決めるシンタックス（構文）及び
セマンテイツクス（意味）を有する。セマンティックス
が、又主効力及び副効力の双方を含む。

主効力は、「主情報」として考えられるデータ値を発生
することができる。こうして、例えば、ＡＤＤインスト
ラクションの主効力は二つの量の加算である。他に、そ
の主効力は非データ動作、例えば、ＪＵＭＰのような制
御のフロー中の変化であることも可能である。

副効力は、ａ）その主効力以外のもので、且つｂ）潜在
的に、プログラム実行中、後で使用可能なインストラク
ションの何らかの効力である。副効力は、例えば、種々
の二次情報を発生することができる。こうして、例えば
、算術的インストラクションの副効力は、しばしば，そ
の値が（０又か非０かのような）算術結果あるいは（結
果がオーバフローしたかどうかのような）動作自体の属
性を示す条件コード・ビットの設定を含む。他に、その
副効力は、二次情報の発生には与からず、むしろ、イン
ストラクションのセマンティックスの特性に与かること
ができる。ある例は、語長レヂスタの高次の半語が、そ
のレヂスタ上で半語の動作が遂行されているとき、保全
されるか否がである。

特定の副効力が、そのプロセッサ設計チームにより意図
されていたか、いなかったかは注意を要する。例えば、
プロセッサ・ファームウェア中のエラーのせいで、特定
のインストラクションの実行の際に常にリセットされる
と想定されている特定の条件コード・ビットが、そのイ
ンストラクションか特定のオペランド値で実行されてい
るとき、非リセット状態に残されることが起きるかも知
れない。

副効力が、プログラム中で使用される仕方は色々である
。例えば、条件コード・ビットの値は、制御のフローを
変えるために、その直後のプログラム・コード・インス
トラクション中に検査を受けることができる。あるいは
、オーバフ口一条件コード・ビットの値が検査を受ける
ことができ、もしセットされていることが見出だされる
と、オバフ口一の場合に対する例外ハンドラーが呼び出
される。これらは、プロセッサ設計チームが彼等の一般
的ユーティリティの理由から装備する、副効力のルーチ
ン的使用の例である。しかしながら、プログラマーは、
しばしば元々意図されていたちの以外に対する特定の副
効力を利用し、実際、この目的に巧妙な副効力を利用す
ることができる。

元々意図されていたちの以外のために、巧妙さは無い特
定の副効力がしようされる例は、システム呼び出しが失
敗したことを呼び出しプログラムに返報する手段として
、システム呼び出しを出力する際の、桁上げ条件コード
の設定である。有益にしようすることができる巧妙な副
効力の例は、半語動作が語長レヂスタ上で遂行されてい
るときに、そのレヂスタの高次の半語が保全されるとい
う事実である。このことが有るので、あるプログラムは
、そのプログラムの部分を代行して実行するためにデー
タをバスするこの効力に依存することができる。実際上
．そのレヂスタの高次の半語は特設半語レヂスタとして
機能する。写像プロセスは、翻訳されつつあるそのプロ
グラムの作成体がそれらに、実際、予見出来ない方法で
依存していたかも知れないので、そのような副効力の全
部を誠実に複製しなければならない。

副効力を写像する旨い方法は次のとおりである。

即ち、トランスレータ写像フェーズの作成中、ソースマ
シン・インストラクション・セットの各インストラクシ
ョンは、その主効力及びその副効力の全部の双方を評価
するために解析される。初期に、そのプロセッサ参照マ
ニュアルまたは他のドキュメンテーションがその副効力
についての情報を集めるために使用される。ついで、基
幹の中間言語表現のシーケンスが各ソースマシン・イン
ストラクションのために開発され得る。このシーケンス
はそのインストラクションの主効力及びその既に知得さ
れている副効力を遂行する中間言語インストラクション
を含む。例えば、ＡＤＤインストラクションに対する基
幹は、種々の条件コード・ビットを計算し且つセットす
る個々の中間言語ステートメント（文）を含むであろう
。ソースマシン及び目標マシンの双方が僅かに類似した
副効力を持つことはできるが、それらの詳細なセマンテ
ィックスは違っていても良い。例えば、一つのマシン上
のＭＯＶＥインストラクションは、他のマシン上の同等
インストラクションが全く条件コド・ビットに影響する
ことができないので、零及び負の条件コード・ビットを
セットすることができる。こうして、好ましい実施例で
は、基幹のシーケンスが、目標マシンの相当する副効力
に依存するよりむしろ、明確にソースマシンの副効力を
複製するであろう。） 副効力の特質も又考慮されなければならない。

例えば、もし、特定の条件コード・ビットが、設計によ
り又はエラーで、特定のオペランド値に対してセットさ
れないと、例えば、これらのオペランド値を検査し、且
つ適切な場合に於いてその条件コード・ビットを無視す
るコードを設けることによって、その基幹中に再生さな
ければならない。

更に、写像されつつあるインス１・ラクションの主効力
上に強い影響を与える副効力も又は考慮されなければな
らない。こうして、例えば、半語加算は、上記で考察し
た例に於いてのように、語長レヂスタの高次の半語の適
切な取扱いを含まなければならない。

（以下余白） 更に、その中間言語コードを、それが各副効力を、それ
が（下記に考察する如く、最適化のコドψエリミネーシ
ョン・フエーズ中）不必要なコドを除くために最大数の
潜在的機会をもたらすので、できる限り他の各副効力を
遂行するものから独立して遂行するように保つ注意が払
われねばならないことに注意を要する。

ソースマシン・インストラクション・セット中の各イン
ストラクションに対する、基幹中間言語コード・シーケ
ンスが、翻訳時に於ける写像フエーズに使用可能である
。こうして、写像は、既に作成されている中間言語コー
ド・リストへの、ａ）各インストラクションのオペラン
ドを取り出すためのコード、ｂ）適当な基幹、及びＣ）
もし必要であれば、そのインストラクションの結果を記
憶するためのコードの加算から成る。

トランスレータの開発中に、特定の副効力がそれらが文
章化されてもおらず明白でもなかったために考慮されな
かったことは旨く、判明し得る。

従って、そのような副効力に依存するアプリケションは
、翻訳されたときに、期待されるようには遂行しないで
あろう。このことは、その中で翻訳されたプログラムの
失敗点が見出だされ、副効力に対しての不明が識別され
、且つ写像プロセスがそれらを考慮するために変形され
る開発を繰り返し必要とする。

最後に、分解フエーズ及び写像フエーズはソースマシン
に依存性があることを指摘することができる。従って、
異なる分解要素及び写像要素が、異なるソースマシンの
各々に対して作成されなければならない。このことは、
製造者のインストラクション・セット・マニュアルを参
照することにより、容易に運ぶことができる。しかしな
がら、解析は、その機能が基本的に分解を管理すること
の一つであるので、マシン非依存性である。

変換 再び、第１２図を参照して、トランスレータの次の要素
、即ち変換が二つのフエーズ、即ち最適化及び合成を持
っていることが見られる。

本発明によれば、上記したように、最適化フ工ズの基本
的機能は拡張されたプログラム・コドを解析し、且つ実
際、適当なプログラム性能に不必要であるインストラク
ションを消去することである。好ましい実施例に於いて
は、より特定的に、その解析及びインストラクション消
去は全般的に遂行される。即ち、特定のインストラクシ
ョンを保持するか又は消去するかの必要性又は不必要性
は翻訳されつつあるプログラムの全体についての検査に
基づいて決められる（例えば、その反対には基本のフロ
ー・ブロック又は手順がある）。

このアプローチは、実際に不必要として識別され得るプ
ログラム・コードの量を最大にする。（事実、このこと
は、拡張されたコードの量が膨大であり、その量を減ら
す各機会を旨く利用するので重要である）。公知の最適
化技術、即ち初期にコンパイラ用に開発された最適化技
術がこの動作を遂行するために例示的に使用される。有
益なことに、そのような最適化技術は実際上、例えばソ
ースマシン・コンパイラによって所定のアプリケション
内に作成されていた遺物を消去することにより、例え、
そのコンパイラが実際にそのような最適化技術を具体化
しなかったとしても、プログラムの質を改良することが
できる。これらの遺物は、例えば、メモリからの到達し
得ないコード及び不必要なロードを含み、且つメモリへ
記憶する。

この最適化フェーズへの入力は、明確化された全副効力
を持ち、第１５図に於ける如く、注釈されたソースアプ
リケーションの中間言語表現である。実際のそのような
プログラム・コードの小部分が第１１図の中間カラムに
示される。

本発明の特徴によれば、更に，これまでに開発され且つ
コンパイラ技術に使用様されているいわゆるデータ・フ
ロー解析技術が、不必要なインストラクションの解析及
び消去を遂行するための翻訳問題に有益に適用できる。

そのうえ、本発明の別の特徴によれば、以下に述べるよ
うに、データ・フロー解析は二つの部分で遂行される。

定義使用のチェイニングのコンパイラ用に開発され得た
技術は、有益なことにデータ・フロー解析を達成するた
めに例示的に用いられる。特に、データ・フロー解析の
目的は、「定義」又は「使用」の何れかであるとして、
中間言語表現中の変数の全叙述が「定義」若しくは「使
用」であるとして分類することである。「変数」は（条
件コード・ビットを含む）レヂスタ、メモリの記憶位置
又はスタックの記憶位置の名称である。「定義」は新し
い値を得るインストラクション内に於ける変数の出現で
ある。「使用」はその変数の他の出現、即ちその定義さ
れた値が使用される場所である。こうして、各使用はあ
る定義（又は一組の定義）によって作成された値の叙述
であり、且つ手順中を通しての可能な制御のフローのパ
スを検査することにより、特定の使用中にその値を発生
することができるであろう一組の定義が推論される。こ
うして、先に簡単に第２１図を見ると、インストラクシ
ョン「Ｚ＝１０」は変数Ｚの定義であり、方、次ぎのイ
ンストラクションｒＸ−ＺＪは変数Ｚの使用である。定
義を使用に結合するプロセスは実際、上記の定義一使用
チェイニングであり、こうして発生された情報は、ここ
では［データ・フロー結果」として言及される。

本発明の特徴によれば、データ・フロー結果はそこで、
例示的に「共通サブ・イクスブッレション（副表現）消
去」、「不変量コード・モーション（行動）」、「定数
伝搬」、「スカラ伝搬」及び「休止コード消去」を含む
、数個のコンパイラ用に開発された変換を遂行する。

休止コード消去は、遂行されるべき最後の変換であり、
使用を持たない定義を含んでいるインストラクションの
除去に関係する。それは、拡大した中間言語バージョン
は使用されることが無い副効力の計算に当てられたイン
ストラクションで一杯になっているため、（翻訳最適化
中に消去され得る数個のインストラクションに関して）
最も有効な変換である。このことは、第１１図に示され
、この図は３カラムで、ソースマシン・プログラム・コ
ードの５本のラインが中間言語コードの３９本のライン
に拡大され、且つ、休止コード消去後、被翻訳コードの
１０本のラインに縮小される仕方を示す。

その最適化が実際に遂行されるときは、他の変換が休止
コード消去に先行する。見られるように、それらの各々
はプログラムの性能を改良する。そのうえ、定数伝搬及
びスカラ伝搬は、ある定義を余剰にし、従って休止コー
ド消去により除去可能にする有益な効果を持っている。

そのような変換は、元のソースマシン・コードを作り出
したコンパイラ中で使用された最適化の質に反比例した
効果を持っている。実際、極く最近まで市販用コンパイ
ラに最適化技術を含めることは一般的ではなかった。そ
れ故、これらの変換は、上記した高い有効性を持った休
止コード消去プロセスとの組み合わせにより、現在、市
販で利用できる大多数のプログラムの翻訳には極めて有
効である。そのうえ、これらの変換はいずれにしても休
止コードを発生される必要があるデータ・フロー結果を
使用するので、最適化プロセスにそれらを導入するのは
、比較的に僅かな計算時間を伴うだけである。

コモン・サブ・イクスプレッション（共通副表現）の消
去は、同じ値を持つ冗長な計算の排除に関係する。共通
副表現は、各計算中の変数が他の計算中の対応する変数
として同じく関連付けられた定義を持つものとして、同
じ変数上に同じ演算を遂行することにより、定義の所定
の対が計算されることを判定することによって識別され
る。こうして、第１６図に示される初期プログラム・コ
ドを検討する。なお、この図において、レヂスタＸは、
加算レヂスタＡ及びＢの結果を割り当てられ、後のレヂ
スタＹも又、加算レヂスタＡ及びＢの結果を割り当てら
れている。レヂスタＡ及びＢの割り当てへの干渉は無い
ものと仮定する。この加算を二回遂行するのは最適では
ない。したがって、変数＠１が変数Ａ及びＢの加算結果
を保持するために作成される。ついて、変数＠１を参照
して、この加算は、変数Ａ及びＢへの割り当てに置き変
えられる。

不変数コード動作は、ある値の計算がその制御のフロー
中のループ内で遂行される場合に関係する。もし、その
計算に関係する使用が、そのルプ外にある関連付けられ
た定義を持つだけてあれば、その計算はそのループ内の
不変数であろう。

即ち、そのループの繰り返し毎に同じ値が計算されるで
あろう。従って、その計算はそのループの前に移すこと
ができ、その結果、それが一回遂行されるだけで、実行
時間（これはコードの規模ではないが）が改善される。

従って、第１７図に示される初期プログラム・コードを
検討する。レヂスタＸは、ＬＡＢＥＬにより定義された
ループ内で加算レヂスタＡ及びＢの結果を割り当てられ
ている。しかしながら、そのループ内のレヂスタＡ及び
Ｂには割り当てが無いものと仮定する。即ち、その計算
中、レヂスタＡ及びＢの使用はそのルブ内に関連付けら
れた定義を持たないものと仮定する。こうして、そのル
ープの各バスに対しては計算を遂行する必要が無くなる
。従って、変数Ａ及びＢの加算結果を保持するために、
変数＠２への割り当てがループ外で作成され、ここでは
それが一回遂行されるだけである。ついで、変数＠２に
関連して、この加算は、そのループ内の割り当てに置き
変えられる。

定数伝搬は、もし、ある使用が唯一の関連付けられた定
義を持ち、且つその定義が引き続いてある変数へのある
定数の割り当てであれば、その使用をその定数で置き換
えることに関係する。従って、第１８図に示される初期
プログラム・コードを検討する。ここで、値「１」がレ
ヂスタＡに割り当てられ、次ぎのインストラクションｒ
Ｘ＝Ａ＋ＢＪがレヂスタＡの内容を使用する。この場合
、この第２インストラクションでのレヂスタＡへの参照
はその値「１」自体に置き換えられる。そこで、そのデ
ータ・フローの結果はその使用と考察中の定義との間の
関連付けを解除するために更新される。次ぎの休止コー
ド消去変換は、その定義に対する使用が見出だされない
ので、それを余分として削除するであろう。

スカラ伝搬は定数伝搬に似ていて、ここでは、その使用
が再び唯一の関連付けられた定義を持つ。

しかしながら、ここで、その定義は（定数の代わりに）
第一の変数の値の第二の変数への割り当てを構成する。

更に、第一の変数の媒介再定義が無い限り、第二の変数
の使用は第一の変数に関連して置き変えられる。そこで
、そのデータ・フロの結果は適切に更新される。従って
、第１９図に示される初期プログラム・コードを検討す
る。ここで、レヂスタＢの内容はレヂスタＡに割り当て
られ、次ぎのインストラクションｒＸ＝Ａ＋ＩＪがレヂ
スタＡの内容を使用する。この場合、（レヂスタＢへの
媒介割り当てが無い限り）この第二インストラクション
でのレヂスタＡへの参照はレヂスタＢの内容への参照に
置き換えられる。上記の如く、このときは、レヂスタＡ
の使用と考察中の定義との間の関連付けを除去するため
に（且つ、データ・フローの結果を正確に保ち、レヂス
タＢの新しい使用とその使用に関連付けられた定義との
間に関連付けを加えるために）、そのデータ・フローの
結果が更新される。元の定義は、定義が、実際、媒介割
り当てが有る少なくとも一個の他の使用を持っているか
どうかによって、余分に成ったり成らなっかたりする。

もし何も無ければ、その定義は、（次ぎの）休止コード
消去によって削除されるであろう。

以下に詳細に考察し、且つ第１２図に示されるように、
最適化フェーズの変換要素は、本発明の特徴に従って、
手順毎のベースでのソースアプリケーションを有する。

これに対する理由は、最適化されつつあるプログラム・
ユニットの規模が増大するので、最適化のために使用さ
れたデータ・フロー解析技術が、実行時間及びスペース
の爆発的な増加を持つためである。最適化を手順の規模
のユニットに限定することにより、その増加の問題を管
理可能なレベルに保つことができる。しかしながら、こ
のアプローチは、ある手順内に他の手順に対する呼び出
しが存在することに特別な考慮を払なければならないこ
とを意味する。この理由では、最初の手順内で為された
定義は、それによって呼び出された第二手順内の使用を
持つかも知れず、又その反対も有り得る。それで、定義
一使用チェイニング・プロセスはこのことを考慮しなけ
ればならず、さもないと翻訳プロセス全般が不正確なコ
ードを生じることになろう。

これに関して、正確性を確保する一つの方法は、各変数
が各手順呼び出し内で使用され、且つ定義されることを
盲目的に想定することである。こうして、例えば、もし
呼び出し手順内の定義が、（呼び出し手順ではなくて）
呼び出された手順内で実際に使用されると、各定義が呼
び出された手順内で使用されているという盲目的想定は
、考察中の定義が休止コード消去中に除去されないこと
を確定することになろう。他の例として、呼び出し手順
内の定義が、あるレヂスタにある一定値を割り当てるこ
とであり、それでそのレヂスタの内容が呼び出し後にそ
の呼び出し手順内で使用されると想定する。更に、その
呼び出された手順がそのレヂスタの内容を定義し直すと
想定する。全てがその呼び出された手順により定義され
るこの盲目的想定によって、呼び出し手順内でのこの使
用はその呼び出しの先に、その中に現れる定義に関連付
けられないであろうことが確実になり、こうして、定数
伝搬の間違ったアプリケーションが防止される。

他方、上記したように、このアプローチは正確性を保証
する。即ち、コード消去がローカルな環境では不必要で
あると思われ、あるもっと全般的な環境では実際に必要
とされるが、そのコード消去は無いであろう。他方、そ
のような想定は、普通余りにも悲観的であり、最適化の
効果を大きく縮小する。

更に本発明の特徴によれば、より有効なアプローチは、
最適化プロセスを動かすためにいわゆる呼び出しツリー
を使用することである。特に、呼び出しツリーは、その
プログラムの手順呼び出し動作の静的な反映である。そ
のプログラムの入口点での手順はそのツリーの「根」で
ある。（普通、アプリケーションは一つの入口点のみを
持ち、従って、直観的に期待されるように一つの根のみ
が有る。）その根によって呼び出された各手順はそのツ
リーの「枝」であり、枝によって呼び出された各手順は
その枝の「支枝」である、等々。他の手順の呼び出しを
しない手順は「葉」と呼ばれる。

所定の手順から一つ以上の呼び出しによって到達し得る
一組みの手順は、その「子孫」であり、それは逆に「先
祖」である。

第２０図は、例示的な呼び出しツリーを示し、それはそ
の根として、ｒＭＡＩＮＪとして知られている手順、及
びその子孫として、ＰＲＯＣ　　Ａ，ＰＲＯＣ　　Ｂ，
，，．ＰＲＯＣ　　Ｋとして知られている手順を持って
いる。こうして、例えば、ＭＡＩＮはＰＲＯＣ　　Ａを
呼び出し、それは順にＰＲＯＣ　　ＢＳＰＲＯＣ　　Ｃ
を呼び出す。他の例としては、ＰＲＯＣ　　ＤがＰＲＯ
Ｃ　　Ｆを呼び出し、それは順にＰＲＯＣ　　Ｒを呼び
出す。後者は、再帰的にＰＲＯＣ　　Ｄを呼び出す。

データ・フロー解析ステップは、全ての手順を二度、一
度目は呼び出しツリーを順方向に、即ち、根から葉へ、
そして二度目は呼び出しツリーを逆方向に、即ち、葉か
ら根へ、処理する。こうして、一度目のパスに於ける処
理の例示的順序は、ＭＡＩＮ，ＰＲＯＣ　　Ａ，ＰＲＯ
Ｃ　　Ｂ，ＰＲＯＣＣ，ＰＲＯＣ　　Ｄ，ＰＲＯＣ　　
ＦＳＰＲＯＣ　　Ｅ，ＰＲＯＣ　　Ｈ，ＰＲＯＣ　　Ｇ
，ＰＲＯＣ　　Ｉ，ＰＲＯ’Ｃ　　ＫそしてＰＲＯＣ　
　Ｊである。二度目のバスに於ける処理の例示的順序は
、ＰＲＯＣ　　Ｂ，ＰＲＯＣ　　Ｄへの再帰アークはこ
れらの順序を確立する際に無視されていることは注目さ
れる。実際、そのような再帰サイクルに関わる呼び出し
ツリーの部分にデータ・フロー解析遂行するとき、呼び
出しに関して、定義一使用チェイニングは極端に複雑に
なるかも知れない。この理由は、上記した、各変数が各
呼び出された手順内で使用され且つ定義される悲観的な
想定は、典型的にその呼び出しツリーのそのような部分
のために使用される。こうして、ＰＲＯＣ　　ＤＳＰＲ
ＯＣ　　Ｆ及びＰＲＯＣ　　Ｒ，及びそれらのお互いの
呼び出しを含む、第２０図の呼び出しツリーのその部分
はこの様式で取り扱われる。しかしながら、ＰＲＯＣＦ
からＰＲＯＣ　　Ｉ｛及びＰＲｏＣ　Ｉへの呼び出しは
、なお以下に述べるように（即ち、再帰サイクルに繋が
れていない手順と同じ方法で）処理することができる。

二つのデータ・フロー解析の使用は、定義一使用チェイ
ニングが、所定の手順を呼び出す手順及びそれが呼び出
す手順の双方を、ａ）定義一使用チェイニングを容認で
きない程の実行時間及びスペースの犠牲で全般的に遂行
したり、又はｂ）最適化を大きく弱める最悪の想定を、
これらの関係について為す必要無しに、考慮することが
できるようにする有益な目的に役立つ。こうして、その
呼び出しツリーに亘って複数のバスを使用することは翻
訳プロセスを扱い易くしている。それは又、プログラム
によって要求されるメモリ空間に肯定的に影響を及ぼし
且つ実行性能を改善する。最初のデータ・フロー解析パ
スは、ａ）それによって呼び出された手順によって少な
くとも潜在的に定義され、且つ、ｂ）その呼び出しの後
、その呼び出し手順中に使用される手順中で使用される
これらの変数のリストの規準に宛てられる。このリスト
は、呼び出された手順中の変数の定義がそれらを使用す
る呼び出し手順のために保全されねばならない、変数リ
ストの第一の近似である。この近似は、呼び出された手
順中で実際に起きるこれらの定義のみを含むように、後
で第二のパス中で純化される。（呼び出しツリーの葉に
対しては、この純化は第１パス中でなされ得るが、この
実施例ではそうではない。） 順方向パス中の各手順の処理は第２１図に、例示され、
この図は、第２０図の呼び出しツリーに示される二つの
手順、ＲＯＣ　　Ｋ及びＰＲＯＣＪの基幹を示す。その
後者は前者の途中で二度呼び出される。見られるように
、ＰＲＯＣ　　Ｊに対するリストに対してＰＲＯＣ　　
Ｋの第一パス・データ・フロー解析は、変数Ａ，Ｂ，Ｒ
，Ｘ及びＹが全て上記規準に合致することを見出だすこ
とになるであろう。なお、種々の手順中で現れるこれら
の変数については以下に述べる。即ち、それらは潜在的
にＰＲＯＣ　　Ｊによって定義され、それらへの呼び出
しの後で使用される。ＰＲＯＣ　　Ｊの次の第二パス・
データ・フロー解析は、実際にＰＲＯＣ　　Ｊで定義さ
れたリスト上の最適の変数である単一の変数Ｘに対する
このリストを純化するであろう。

同様にして、ＰＲＯＣ　　Ｋを呼び出す手順の以前の処
理は、変数Ｗ，Ｒ及びＹからなるＰＲＯＣＫのための使
用リストの規準に帰着している。

ＰＲＯＣ　　Ｒの次の第二バス・データ・フロー解析は
、実際にＰＲＯＣ　　Ｋで定義されたリスト上の最適の
変数である二つの変数Ｗ及びＹに対するこのリストを純
化するであろう。

上記のように、データ・フロー解析の第二ステップは変
数の明確な各叙述を見出だし、且つ各々を、定義の記憶
位置か又は使用の記憶位置であるとして、分類すること
である。このことは、第２１図に、定義のリストと使用
が各プログラム・インストラクションで現れている二カ
ラムで反映されている。

又「使用ｊカラムに含まれて、いわゆる非明示の使用の
括弧内に記述項が有る。これは、ＰＲ０Ｃ　　Ｋを呼び
出す手順についての第一パスを処理中に、この処理が進
行するに連れ、それによって潜在的に定義されて明らか
になるであろう方法で、識別された変数のリストである
。こうして、第２１図に示されるように、ＰＲＯＣ　　
Ｋを呼び出す手順についての、ＰＲＯＣ　　Ｄ及びＭＡ
ＩＮ（第２０図）のような、第一パスのを処理は、ＰＲ
ＯＣＲによって潜在的に定義されるとき、変数Ｒ１Ｗ及
びＹの識別を完了している。

第二パス・データ・フロー解析は、先ず各呼び出しを、
その手順中に使用を持つすべての変数の定義の記憶位置
であるとして、分類する。これらは、非明示の定義と名
付けられ、ＰＲＯＣ　　Ｊへの呼び出しの各々からＰＲ
ＯＣ　　Ｊへ亘る「定義」カラム内の括弧内に示される
。Ａ，Ｂ，Ｒ，Ｗ，Ｘ，Ｙ及びＺは全て、ＰＲＯＣ　　
Ｋ内に使用を持ち、各ＣＡＬＬＰＲＯＣ　　Ｋインスト
ラクションは、先ずこれらの変数の各々の非明示の定義
の記憶位置として見做される。この最初の分類は、呼び
出し内の定義について、上記の悲観的想定を具体化する
。即ち、この点で、各呼び出しは呼び出し手順内で叙述
された各変数を定義することが想定あれなければならな
い。

次のステップは、各使用を一つ以上の定義と関連付ける
ために、定義一使用チェイニングを遂行することである
。（この例では示されていないが、が、一つ使用に対し
多数の定義が存在することは、各々がそれに当てはまる
の変数の定義を含んでいる、一繋がりになった幾つかの
基本ブロックのチェーン内に有る、ある基本ブロック内
に含まれる使用の結果として生じる。）特定の使用と特
定の定義との関連付けは、第２１図に、各使用をその明
らかな定義と繋ぐ線で示される。例えば、インストラク
ションｒＸ−ＺＪでのｒＺＪの使用は、早期にインスト
ラクションｒＸ−１ＯＪ内で定義される。更に、インス
トラクションｒＡ−ＹＪでのｒＹＪの使用は、早期に最
初のインストラクションＣＡＬＬＰＲＯＣ　　Ｊ内で定
義（少なくとも、この点で想定）される。そのうえ、Ｐ
ＲＯＣ　　Ｋ内のＲＥＴＵＲＮインストラクションに於
けるｒＹＪの非明示な使用が、早期にインストラクショ
ンｒＹ−Ａ＋ＢＪ内で定義される。

最後に、各呼び出しが検査され、それに関連付けられた
使用を持つ定義が呼び出されつつある手順の戻りインス
トラクションに関連付け非明示な使用のリストに加えら
れる。こうして、ＰＲＯＣＫの第１バス処理の終端で、
変数Ａ，Ｂ，Ｒ，Ｘ及びＹはＰＲＯＣ　　ＪのＲＥＴＵ
ＲＮインストラクションに記録される。これは、ＰＲＯ
ＣＫの見地から、ＰＲＯＣ　　Ｊによって定義すること
ができる最良の推量を表す。Ｗ及びＺは、ＰＲＯＣＪに
対する呼び出し後は明示の使用を少なくとも媒介定義な
しでは持たず、それらは、ＰＲＯＣＪの終了点でＲＥＴ
ＵＲＮと関連付けられた使用を非明示の使用のリストに
含まれない。更に、ＰＲＯＣＫ内に非明示の定義及び使
用のみを持つ変数Ｒが、未だそのリストに含まれている
ことが注目される。実際、上記で考察したように、変数
ＲがＰＲＯＣ　　Ｒを呼び出す何らかの手順によって使
用され、この点で、変数がＰＲＯＣ　　Ｊ内で定義され
得ることが想定されるに違いないのでそのことは適切で
ある。（何故なら、ＰＲＯＣＪは未だ検査されておらず
、確定した答えは未だしられていない。） この点で、ＰＲＯＣＫの第１パス処理は完了し、この処
理は、ａ）この点で、ＰＲＯＣ　　Ｊによって定義され
るものと想定されなければならず、且つ、ｂ）ＰＲＯＣ
　　Ｊに対する呼び出し後に使用される、ＰＲＯＣＫ内
で使用されたこれらの変数を識別するその仕事を完了す
る。ＰＲＯＣＪは呼び出しツリーの葉であるので、それ
は呼び出しを含まず、且つ、実際、第一バスは呼び出し
に関する情報を集めることに当てられているので、ＰＲ
ＯＣ　　Ｊ又は第一バス内のその他の葉を処理する必要
は無い。

第二の、データ解析ステップによる呼び出しツリーを通
る逆方パスは、各手順のデータ・フロー解析を再び全体
に亘って遂行するが、ここでは、ちょうど述べた如く、
第一バス内で集められた情報は使用しない。特に、その
定義一使用チェイニングは、スクラッチから再び、遂行
されるが、しかしここでは各手順に対して開発された非
明示な定義及び使用の純化されたリストを合同させる。

そのバスは逆順であるので、ＰＲＯＣ　　Ｊ及びその処
理結果は、第２２図で示される。この図で示されるよう
に、ＰＲＯＣＪの第二の、データ・フロー解析の第１ス
テップは、再び、変数の各明示された叙述を見出だし、
それを定義の記憶位置又は変数の記憶位置の何れかであ
るとして分類することである。「使用ｊカラムに含まれ
ているのは、第一バス中に開発された非明示な使用にリ
ストであり、このリストは変数Ａ，Ｂ，Ｒ，Ｘ及びＹは
を持っている。（もしＰＲＯＣ　　Ｊを呼び出す他の手
順が有った場合は、なお他の変数が、これらの変数最初
のパス中に処理されたとき、なお他の変数がそのリスト
に加えられていよう）。

更に、このパスは、その手順の入口点に関連付けられた
非明示な定義のリストを作成するステップを含み、この
リストは、手順内で使用されるが、その中では定義され
ないそれら変数を含んでいる。

特に、ＰＲＯＣ　　Ｊでは、このリストは変数Ｑ及びＳ
から成っている。

第一パスでのように、次のデータ・フロー解析ステップ
は、解析されつつある手順によって呼び出れる全ての手
順に非明示な定義を関連付けることに関わる。しかしな
がら、ＰＲＯＣ　　Ｊは、他の手順は何れも呼び出しせ
ず、従って、このステップでは何のアクションも取られ
ない。

次のステップでは、再び定義一使用チェイニングが遂行
される。第２２図に示すように、変数Ｘの非明示な使用
はインストラクションｒＸ　−　Ｑ　十Ｓ」内でその変
数の定義と関連付けられる。一方、変数Ｑ及びＳの明示
された使用は、ＰＲＯＣ　　Ｋの入口点と関連付けられ
た非明示な定義と関連付けられる。しかしながら、変数
Ａ，ＢＳＲ及びＹは、それらが、ＰＲＯＣ　　Ｋの有利
点から、ＰＲＱＣ　　Ｊで潜在的に定義されていた変数
のリスト内に含まれていた事実にもかかわらず、ＰＲＯ
ＣＪ内には定義を持たない。ここで、第一パスのリスト
は、（第２２図に、それらを通して置かれたスラッシュ
で示すように）これらの変数を捨て、それにより変数Ｘ
を唯一の記述項として残すことによって、純化すること
ができる。実際、変数Ｘは、ＰＲＯＣ　　Ｊに対する呼
び出しに続＜ＰＲＯＣＫ内で使用されるＰＲＯＣ　　Ｊ
内で定義される唯一の記述項である。

ここで、ＰＲＯＣ　　Ｊを通じての第二データ・フロー
解析が完了する。即ち、ＰＲＯＣ　　Ｊ及び他の手順間
の呼び出し関係を考慮しつつ、最終的に且つ正しく到達
している定義の計算が遂行されている。ついで、共通副
表現消去、不変量コード・モーション、定数伝搬、スカ
ラ伝搬及び休止コード消去の次の変換がＰＲＯＣ　　Ｊ
上で遂行され、その手順の最適化が完了する。

結局、第二バスの処理がＰＲＯＣ　　Ｒに遭遇し、ＰＲ
ＯＣ　　Ｊの第二パスの処理に関して上記に略述したと
同様なステップが遂行される。勿論、ＰＲＯＣ　　Ｊと
は違い、ＰＲＯＣ　　Ｋは呼び出しを含む。従って、又
ＰＲＯＣ　　Ｊとは違い、定義がこれらの呼び出しに関
連付けられる。しかしながらここで、それは、第一バス
での場合であったような、ＰＲＯＣ　　Ｋ内で使用され
た全変数のリストよりむしろ、使用されているＰＲＯＣ
　　Ｊに対して先に開発された変数の純化されたリスト
である。ここで、このリストは、それが実際、ＰＲＯＣ
　　Ｊ，この場合単一の変数Ｘによって、定義されてい
るこれらの変数のみを含むので、「完全」である。

更に、非明示な使用のリストは、各手順の呼び出しに関
連付けられる。なおこのリストは、以前、呼び出された
手順に対する第二パス中に開発された非明示な定義であ
る。

こうして、ＰＲＯＣ　　Ｋに於いて、ＰＲＯＣ　　Ｊの
入口点での非明示定義として開発された変数のリストが
、ＰＲＯＣ　　Ｒに於けるＰＲＯＣ　　Ｊのの呼び出し
に対する非明示な使用として使用される。このステップ
は、ＰＲＯＣ　　Ｋ，又はそれを呼び出す手順内の変数
Ｑ及びＳの定義がＰＲＯＣＪに必要なので、必要である
。従って、そのような定義は、それらと関連付けられた
使用を持つことによって、休止コード消去から保護され
なければならない。この例では、変数Ｑ及びＳは、事実
、ＰＲＯＣ　　Ｒで定義されず、且つその結果、それら
がＰＲＯＣ　　Ｊに対して為されたのと全く同様な仕方
で、その手順の入口点に関連付けられた非明示定義のリ
ストに用意される。

定義一使用チェイニングが遂行され、ＰＲＯＣＫに対す
るその結果が再び接続線によって示される。ここで、Ｐ
ＲＯＣ　　Ｊについての純化された情報の使用が、第一
バスでのその計算に比して、定義に到達する計算に幾つ
かの顕著な違いを起こしていたことが注意される。

例えば、インストラクションｒＹ＝Ａ＋ＢＪでの変数Ａ
及びＢの使用は、ＰＲＯＣ　　Ｊに対する第二の呼び出
しての非明示の定義と最早、関連付けられていず、むし
ろインストラクションｒＢ−Ｙ」及び［Ａ＝ＹＪでのこ
れらの変数の区域的定義に関連付けられている。次の共
通副表現変換は、第１６図に厳密に示すように、こうし
てインストラクションｒＸ＝Ａ＋ＢＪ及びｒＹ＝Ａ十Ｂ
Ｊが共通副表現であり、且つ最適化に対する候補である
として認知することができるであろう。更に、変数Ｒは
最早、ＰＲＯＣ　　Ｊの呼び出しによって定義されると
は想定されないので、ＰＲＯＣ　　Ｒの出力点でのそれ
らの非明示使用も最早、何らの関連付けられた定義を持
たず、非明示使用のリストは、（第２２図に、「Ｒ」を
貫いて置かれたスラッシュで示すように）その変数を除
外するように純化することができる。ちょうど考察した
ばかりの変数Ａ及びＢの場合との直接的な類比で、ＰＲ
ＯＣ　　Ｋの出力点に於ける非明示使用リストからの変
数Ｒの消去は、変数Ｒが最早、ＰＲＯＣＫで定義ざれる
べきこれらの呼び出し手順によって想定される変数のリ
スト上に現れないであろうから、ＰＲＯＣＫを呼び出す
手順の最適化を弓き続き与かるであろう。

又、ＰＲＯＣ　　Ｋ内の変数Ｘの四つの定義のうち三つ
、即ち、定義ｒＸ−ＺＪ、ｒＸ−Ａ＋ＢＪ及び第二〇Ｃ
ＡＬＬＰＲＯＣ　　Ｊインストラクションに関連付けら
れている使用は無いことが注意される。こうして、これ
ら三つのインストラクションの全ては休止コード消去に
よって削除されよう。（インストラクションｒＸ−Ａ＋
ＢＪは、共通副表現消去ステップによって、第１６図に
示すような形態ｒＸ−＠ＩＪに変換されているであろう
が、それにも拘らず、関連付けられた使用が欠乏してい
るため、休止コード消去によって削除されるであろう。

） ＰＲＯＣ　　Ｋを通してのデータ・フロー解析の第二バ
スも又、ここで完了する。こうして、共通副表現消去、
不変量コード・モーンヨン、定数伝搬、スカラ伝搬及び
休止コード消去はＰＲＯＣＫ上で遂行され、その手順の
最適化が完了する。

ここで、第１２図に戻って、その最適化の変換要素の最
終フエーズが「合成」であることを見てみよう。変換の
この合成フエーズの全般的ゴールは、現に動作している
アセンブリ言語表現よりは元のコンパイラ・ソース言語
に近いプログラム表現を発生することである。このよう
にすることは、目標マシンの資源及び能力を効果的に使
用するためにより大きな機会を持ったコード発生要素を
提供するであろう。このことは、翻訳されたプログラム
の規模と実行速度（性能）の双方とも改良する。

この目的のため、変換の合成フェーズは、それらが現に
中間言語に変換されているソースマシン目的コードであ
るそれらより効率的に表現し得るｒ高レベル」機能とし
て認め得る中間言語構造のシーケンスを探す。例えば、
ソースマシン・プロセッサは直接、３２ビット乗法演算
を遂行することはできず、むしろそれを遂行するための
一連のインストラクションを必要とするものと想定する
。

しかしながら、目標マシンは直接、３２ビット乗法演算
を遂行することはできる。その合成フェズは、インスト
ラクションのパターンが実際、３２ビット乗算を構成し
ていることを認知し、、且つ中間言語バージョンに於け
る適切な単一インストラクションを代行するように設計
することができる。他の例は、Ｃ言語「交換」文、パス
カル「格」文、折り返し論理構成、等である。

合成フェーズに使用できる認知可能シーケンスのレハー
トリは、翻訳ソフトウェアの開発中、ソースマシン及び
目標マシンの設備及び元の目的コードの特徴を検査する
ことによって、経験的に開発されている（勿論、それら
は最初の位置でソスマシンのアプリケーション目的コー
ドを発生したコンパイラの特徴に依存する）。

要するに、共通副表現消去、不変量コード・モーション
、定数伝搬、スカラ伝搬及び合成は、本質的に、同等で
小さいインストラクションのグループをで置き換え得る
、拡大したインストラクションのグループを識別するパ
ターン認識技術である。不変量コード・モーションはパ
ターン認識技術の別のタイプである。これは、拡大した
インストラクションの数を減らしはしない。しかしなが
ら、これは、インストラクションのシーケンスが。

前記第二バージョン内のインストラクションの順序換え
された同等なシーケンスを識別することによって、その
インストラクション、により効率的な順序換えをおこな
う。

コード発生 翻訳プロセスのコード発生フェーズは、実質的に伝統的
なコンパイラのコード発生フエーズと同じである。即ち
、上記したように最適化された、アプリケーションの中
間言語バージョンは、各中間言語インストラクションに
一つ以上の適切な目標マシンのアセンブリ言語インスト
ラクションを置き換えることによって、目標マシンのア
センブリ言語へ変換される。そこで、その結果のコード
は、目標マシンの目的コードにアセンブルされ、翻訳さ
れたシステム・ソフトウェアと結び付けられる。　　　
　　　　一Ｐ／３９、Ｌ／２一第２３図は、翻訳された
アプリケーションが翻訳されたシステム・ソフトウェア
及び目標マシンシステム・ソフトウェアと結び付けられ
る方法を例示的に示す。このような情況においては、用
語「結び付け」は、ソフトウエア内の記号アドレスを究
極的に、プロセッサが動作することができる実際のアド
レスに変換するブロッセスに関係する。

より明確には、この分野で極めて伝統的であるように、
この結び付けは、例示的には二つのステージ内に在る。

第一ステージでは、「連結」として知られているように
、（翻訳されたシステム・ソフトウェアのような）第二
目的コード・モジュールの入口点への（被変換アプリケ
ーションのような）第一目的コード・モジュール内の記
号基準が、結合された目的プログラムの第一アドレスに
に関して、そのような入口点の全てにラベル付けする数
値オフセットに変換される。第二ステージは、いわゆる
「ローディング」プロセス内に包含されており、このス
テージでは、その後、それらのオフセットが、プロセッ
サが動作することができるアドレスに変換される。

ついで、第１２図では、その第一カラムが三つの目的モ
ジュール、即ち、被変換アプリケーション、翻訳された
システム・ソフトウェア及び目標マシンのシステム・ソ
フトウェアをコンパイルされた形態で示す。この点でモ
ジュールの各々は、それ自体のセットでＯｘＯで始まり
、それぞれＯｘｌ０００、Ｏｘ２００及びＯｘ６００で
終了するアドレス記憶位置を持つものとして考えること
ができる。

その被変換アプリケーションは、例示的にそのアプリケ
ーションにたいして内部的である手順ＰＲＯＣ　　Ｊに
対する呼び出しを有する。こうして、そのトランスレー
タの、この事項に関してはコンパイラ機能を奏するコー
ド発生要素は、ＯＸ２００に於けるＰＲＯＣ　　Ｊに対
する基準を識別できていて、中間言語コード中のｒＰＲ
Ｏｃ　　ＪＪの叙述であったものを、そのモジュールの
出発点、即ち例示的にはＯｘ８００である入口点に関し
て、ＰＲＯＣ　　Ｊの入口点の記憶位置を表示するオフ
セットに置換し終わっている。

更に、その被変換アプリケーションは、それぞれ翻訳さ
れたシステム・ソフトウェア及び目標マシンのシステム
・ソフトウェアのプログラムである、システム・サービ
スＳＥＲＶＩＣＥＩ及びＳＥＲＶ　Ｉ　ＣＥ２に対する
二つの呼び出しを含む。

これらは被変換アプリケーションの外部に有る基準プロ
グラムを呼び出すので、ＳＥＲＶＩＣＥＩ及びＳＥＲＶ
ＩＣＥ２の叙述はコード発生部によって「解明」、即ち
オフセットに置換され得ない。

同様に、目標マシンのシステム・ソフトウエア内のシス
テム・サービスＳＥＲＶＩＣＥ３に対する翻訳されたシ
ステム・ソフトウェア内の基準はこの点で解明されずに
残る。

第２３図の第二カラムは、リンキング（結び付け）後の
三モジュールを示す。とりわけ、リンカ（結び付け部）
はこれら三モジュールを、ＯＸＯからＯｘ８００までの
単一のアドレス・スペクトラムに組み合わせており、且
つ各インストラクションはそのスペクトラム内にアドレ
スを持っている。こうして、ここでは、翻訳されたシス
テム・ソフトウェアの第一アドレスはＯｘｌＯＯＯであ
り、一方、目標マシンのシステム・ソフトウエアの第一
アドレスはＯｘｌＯ００である。ＳＥＲＶＩＣＥＩ、Ｓ
ＥＲＶＩＣＥ２及びＳ　ＥＲＶ　Ｉ　ＣＥ３に対する種
々の記号基準は、リンクされたモジュールの開始点に関
してそれぞれ計算されたオフセット、即ちＯｘｌ０００
、Ｏｘｌ３００及びＯｘｌ６００で置換され得る。

あるコンピュータ・システムでは、言わば、呼び出しイ
ンストラクションが、実際のアドレス実行中、そのオフ
セットを呼び出しインストラクション自体のアドレスに
加えることによって決定される際に、結び付け部によっ
て与えられたオフセットが、プログラム実行のための適
切な基礎、即ち、オフセットによって識別されたプログ
ラム・コードのメモリ内の実際のアドレスを提供する。

こうして、例えば、第二の翻訳されたアプリケーション
の呼び出しに於けるオフセットＯｘ８００は、制御のフ
ローが記憶位置ＯｘｌＯ００へ移行すべきことを判定す
るために、その呼び出し自体の記憶位置Ｑｘ２００に加
えられる。しかしながら、本発明の例示的実施例では、
プロセッサは、実行可能コードが、オフセットよりむし
ろアドレスを含むことを必要とする。これは、そのコー
ドが実行のためにＲＡＭにロードされるとき、そのコー
ドをロードする実際の開始ＲＡＭアドレスを各オフセッ
トへ単に加えることによって、適応される。こうして、
第２３図の第三カラムに示すように、そのリンクされた
モジュールは記憶位置ＯＸ５００へ始まるＲＡＭにロー
ドされていて、ここで、全ての呼び出しが、その呼び出
しの目標として、Ｏｘ５０００の適切なオフセットとの
和によって与えられた計算済みのアドレスを識別する。

他の実施例 前記は、単に本発明の原理を示す。

例えば、図示し且つ上記した例示的実施例では、ソース
マシン及び目標マシンは本質的に異なるインストラクシ
ョン・セットを持つ本質的に異なるインストラクション
を持っている。しかしながら、これは、二つのプロセッ
サが共通のプロセッサ・ファミリに属している場合であ
ってもよい。従って、同じインストラクション・セット
を持つが、しかし、そのプロセッサの一つは、例えば２
４ビットのアドレス空間を有し、且つ他のプロセッサの
一つは、３２ビットのアドレス空間を有することができ
る。こうして、この翻訳はインストラクションの小部分
の変換のみに関わることもできる。

他の例としては、図示し且つ上記した例示的実施例に於
いて、本発明に従って、目標マシン上で実行し且つ翻訳
されたシステム・ソフトウェアを呼び出すアプリケーシ
ョンは、それ自体が翻訳されたプログラムである必要は
無い。例えば、ソースマシン及び目標マシンは、同等な
プロセッサのタイプを使用することができ、従って、そ
のソースマシン用にコンパイルされているアプリケーシ
ョンは、翻訳される必要無く目標マシン上で実行可能で
あろう。しかしながら、その二つのマシンのシステム・
ソフトウェアとアドレス空間の双方又は一方は相違して
いていてもよい。こうして、翻訳不必要なアプリケーシ
ョンを目標マシン上での実行のための翻訳されたシステ
ム・ソフトウェアにリンクすることは有益であろう。

更に、ここで説明した本発明は、翻訳されつつあるプロ
グラムの目的コード・バージョンに対して動作するが、
入力プログラムは、別に例えば、ａ）そのアセンブリ言
語バージョンであってもよく、又はｂ）ソースマシン上
で通訳するように意図された形態になっている、いわゆ
る通訳コードに含まれていてもよい。後者の例には、Ｕ
ＣＳＤパスカルＰ−コード・コンパイラによって出力さ
れるプログラムが有る。幾つかの場合、相違する中間ア
センブリ言語は必要でないかも知れない。

それで、元のアセンブリ言語又は他のインストラクショ
ン・セットに関しては、むしろ拡大が遂行され得る。更
に、翻訳されたプログラムを目標マシンの目的形態にコ
ンパイルするより、むしろ（通訳要素を用いて）アセン
ブリ形態に実行することが望ましいかも知れない。

従って、この分野での技術者が、ここには明示的に示さ
れ或いは述べられていないが、本発明の原理を含み、従
ってその精神及び範囲に有る、多くの構成を案出し得る
ことが理解されよう。

【図面の簡単な説明】

図面に於いて： 第１図は、例示的なソースコンピュータのブロック・ダ
イアグラムを示す図； 第２図は、例示的な翻訳コンピュータのブロツク・ダイ
アグラムを示す図； 第３図は、例示的な目標コンピュータのブロック・ダイ
アグラムを示す図・ 第４図は、典型的なソースコンピュータ及び目標コンピ
ュータのアドレス空間を示す論理図；第５図は、目的コ
ードのハードウエア・エミュレーション及びソフトウエ
ア・エミュレーションを示す論理図； 第６図は、目的コード翻訳のオフライン・フェズを示す
論理図； 第７図は、目的コード翻訳の実行時フエーズの一形態を
示す論理図； 第８図は、目的コード翻訳の実行時フェーズの第二形態
を示す論理図； 第９図は、第８図に示す仮想ハードウェア項目モニタの
動作を示すフロー・チャート；第１０図は、被翻訳ソフ
トウェアを作成し且つ実行する全般的プロセスを例示的
に示すフロチャート； 第１１図は、ソースマシンのアセンブリ言語コ一ドの部
分が、トランスレータの分析フエーズ中に拡大され、そ
の後その最適化フェーズ中に圧縮される方法を示す図； 第１２図は、本発明を履行するために使用される例示的
なトランスレータの要素を示すフロー・チャート； 第１３図は、このトランスレータの分析要素を示すフロ
ー・チャート； 第１４図は、このトランスレータの分析要素が、翻訳さ
れているアプリケーションを、いわゆる基本ブロックに
分割する方法を示す図； 第１５図は、いわゆる手順に組み合わされた幾つかの基
本ブロックを示すグラフ； 第１６図乃至第１９図は、トランスレータの最適化要素
中に遂行される、異なる変換を例示するアセンブリ言語
コードの種々の部分を示す図；第２０図は、本発明の特
徴に従い、トランスレタの最適化要素によって使用され
る、いわゆる呼び出しツリーの例を示す図・ 第２１図及び第２２図は、本発明の特徴に従い、トラン
スレータの最適化要素中に遂行される二つのデータ・フ
ロー解析バス中に、プログラム・コードが処理される方
法を示す図；そして第２３図は、被翻訳アプリケーショ
ンを被翻訳システム・ソフトウェア及び目標マシンのシ
ステム・ソフトウェアに結び付ける仕方を示す図である
。 出　願　人：アメリカン　テレフォン　アンドＦＩＧ， Ｘ＝Ａ　本Ｂ Ｙ＝Ａ’Ｂ ＦＩＣ；． ＦＩＧ． Δ＝　１ ×＝＾千８ ａｌ＝Ａ＋Ｂ Ｘ＝Ｅｌ ＋Ｄ２　＝　Ａ　＋８ ＧＯＴＯ　ＬＡＢＥＬ ｘ′＝ ＋　８ ＦＩＧ． （Ａ，Ｂ，Ｒ，Ｗ，Ｘ，Ｙ．Ｚ） ＦＩＧ．　２２ ″Ｐ′Ｆｏｃ−Ｋっ叫騨山（号１１（員羞 倖凧 Ｚ＝１０ ｘ＝ｚ ＣＡＬＬ　　ＰＲＯＣ　　Ｊ 已＝Ｘ Ａ＝Ｙ Ｘ＝Ａ　本８ ＦＩＧ．　２３ ＆か付け前 経先＾ごイ１け４ｔ ロード技

Claims (1)

1. 【特許請求の範囲】 １、その少なくとも一つのインストラクションが主効力
   及び副効力を持つ第１インストラクション・セットによ
   って表されているコンピュータ・プログラムの第一バー
   ジョンを処理する方法に於いて、 前記第一バージョンの少なくとも一つのインストラクシ
   ョンを、前記第一バージョンの前記各インストラクショ
   ンの主効力及び副効力を明示的に複製する複数のインス
   トラクションに拡大するステップ、及び その結果拡大されたバージョンを処理して、消去によっ
   て前記プログラムの機能が影響を受けないインストラク
   ションの個々を消去するステップ とからなることを特徴とするコンピュータ・プログラム
   の第一バージョン処理方法。 ２、前記副効力は二次情報の計算を含み、且つ前記消去
   されたインストラクションは前記プログラムによっては
   使用されない二次情報を計算するインストラクションを
   含むことを特徴とする請求項１に記載の方法。 ３、前記処理ステップは、前記拡大されたバージョン上
   にデータ・フロー解析を遂行して前記個々のインストラ
   クションを識別するステップを含むことを特徴とする請
   求項１に記載の方法。 ４、前記データ・フロー解析ステップは、前記拡大され
   たバージョン上に定義−使用チェイニングを遂行するス
   テップを含むことを特徴とする請求項３に記載の方法。 ５、前記データ・フロー解析ステップは、前記拡大され
   たバージョン上に、全般的に遂行されることを特徴とす
   る、請求項３に記載の方法。 ６、前記処理ステップは、前記拡大されたバージョン内
   の手順を識別するステップを含み、且つ前記データ・フ
   ロー解析ステップは、手順毎のベースで前記拡大された
   バージョン上に、全般的に遂行されることを特徴とする
   請求項３に記載の方法。 ７、前記データ・フロー解析ステップは、手順中に生じ
   る変数の定義の中から、少なくとも一つの他の手順で使
   用される定義を見出だすステップを含むことを特徴とす
   る請求項６に記載の方法。 ８、前記手順の少なくとも一つは、変数の値が少なくと
   も一つの前記他の手順内に使用を持つ、その変数の値の
   定義を含み、且つ前記データ・フロー解析ステップは、
   そのような定義をそのような使用に関連付けるステップ
   を含むことを特徴とする請求項８に記載の方法。 ９、前記関連付けステップは、少なくとも第一及び第二
   のデータ・フロー解析ステップを使用することによって
   遂行されることを特徴とする請求項８に記載の方法。 １０、前記処理ステップは、更に前記手順内での呼び出
   し関係を識別する呼び出しツリーを作成し、且つ前記関
   連付けステップは、シーケンス的に、前記手順を呼び出
   しツリーの順方向に処理して、ａ）それが呼び出す手順
   によって少なくとも潜在的に定義され、且つｂ）その呼
   び出し後に、その呼び出し手順内で使用される手順内で
   使用されたそれら変数のリストを作成するステップ、前
   記手順を呼び出しツリーの逆方向に処理して、前記リス
   トから前記呼び出された手順によっては実際に定義され
   ていない変数を除外するステップ とを含むことを特徴とする請求項８に記載の方法。 １１、前記処理ステップは、前記第二バージョン内の同
   等で少ないグループのインストラクションによって置換
   され得る前記拡大されたバージョンのインストラクショ
   ンのグループを識別するために、少なくとも第一のパタ
   ーン認識技術の使用を含むことを特徴とする請求項１に
   記載の方法。 １２、前記処理ステップは、前記第二バージョン内の同
   等な順序直しされたシーケンスのインストラクションに
   よって置換され得るインストラクションのシーケンスを
   を識別するために、少なくとも第一のパターン認識技術
   の使用を含むことを特徴とする請求項１に記載の方法。 １３、前記拡大されたバージョンは、前記第１バージョ
   ンを表す言語と異なる中間コンピュータ言語によって表
   されていることを特徴とする請求項１に記載の方法。