(57)【特許請求の範囲】
【請求項１】
コンピュータ処理による、プログラムのソースコードの変換方法であって、
前記ソースコードをスキャンし、複数の制御が合流するところ、または、制御が複数に分岐するところで前記ソースコードを区切ることによって、前記ソースコードを基本ブロックに分割するステップと、
前記分割された基本ブロックを処理の流れに従って接続し、制御フローグラフを作成するステップと、
前記フローグラフの始点から終点に至る経路に沿って前記ソースコードをスキャンすることによって、値をストアされる変数と、参照される変数を判別するステップと、
値をストアされるよりも前に参照される変数を検出するステップと、
前記値をストアされるよりも前に参照される変数にストアするコードを含むラッパコードを生成して、前記ソースコードに付加するステップを有し、
前記ラッパコードが、前記値をストアされるよりも前に参照される変数に、値をストアするコードと、前記プログラムを呼び出すコードと、前記プログラムを呼び出した後に、前記値をストアされるよりも前に参照される変数を参照するコードを含む、
プログラム変換方法。
【請求項２】
前記ソースコードが、前記プログラムの逆アセンブルによって得られたものである、請求項１のプログラム変換方法。
【請求項３】
前記ラッパコードが、アセンブリ・コードである、請求項２のプログラム変換方法。
【請求項４】
前記ソースコードが、前記プログラムの逆コンパイルによって得られたものである、請求項１のプログラム変換方法。
【請求項５】
前記ラッパコードが、高級言語のソース・コードである、請求項４のプログラム変換方法。
【請求項６】
コンピュータ処理による、プログラムのソースコードの変換システムであって、
前記ソースコードをスキャンし、複数の制御が合流するところ、または、制御が複数に分岐するところで前記ソースコードを区切ることによって、前記ソースコードを基本ブロックに分割する手段と、
前記分割された基本ブロックを処理の流れに従って接続し、制御フローグラフを作成する手段と、
前記フローグラフの始点から終点に至る経路に沿って前記ソースコードをスキャンすることによって、値をストアされる変数と、参照される変数を判別する手段と、
値をストアされるよりも前に参照される変数を検出する手段と、
前記値をストアされるよりも前に参照される変数にストアするコードを含むラッパコードを生成して、前記ソースコードに付加する手段を有し、
前記ラッパコードが、前記値をストアされるよりも前に参照される変数に、値をストアするコードと、前記プログラムを呼び出すコードと、前記プログラムを呼び出した後に、前記値をストアされるよりも前に参照される変数を参照するコードを含む、
プログラム変換システム。
【請求項７】
前記ソースコードが、前記プログラムの逆アセンブルによって得られたものである、請求項６のプログラム変換システム。
【請求項８】
前記ラッパコードが、アセンブリ・コードである、請求項７のプログラム変換システム。
【請求項９】
前記ソースコードが、前記プログラムの逆コンパイルによって得られたものである、請求項６のプログラム変換システム。
【請求項１０】
前記ラッパコードが、高級言語のソース・コードである、請求項９のプログラム変換システム。
【請求項１１】
コンピュータ処理による、プログラムのソースコードの変換プログラムであって、
前記コンピュータをして、
前記ソースコードをスキャンし、複数の制御が合流するところ、または、制御が複数に分岐するところで前記ソースコードを区切ることによって、前記ソースコードを基本ブロックに分割するステップと、
前記分割された基本ブロックを処理の流れに従って接続し、制御フローグラフを作成するステップと、
前記フローグラフの始点から終点に至る経路に沿って前記ソースコードをスキャンすることによって、値をストアされる変数と、参照される変数を判別するステップと、
値をストアされるよりも前に参照される変数を検出するステップと、
前記値をストアされるよりも前に参照される変数にストアするコードを含むラッパコードを生成して、前記ソースコードに付加するステップを実行させ、
前記ラッパコードが、前記値をストアされるよりも前に参照される変数に、値をストアするコードと、前記プログラムを呼び出すコードと、前記プログラムを呼び出した後に、前記値をストアされるよりも前に参照される変数を参照するコードを含む、
変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プログラムの動作を検証するための技法に関する。より詳しくは、この発明は、プログラムの動作の検証のために、動作の再現性を高めることに関する。
【背景技術】
【０００２】
自動車は、もともとはエンジンと機構部品とからなり、主として機械的な操作により、速度制御や走行制御されていた。しかし、１９７０年代頃から、主として、エンジンを効率的に制御するために、電子制御が採用され始めた。このような電子制御のための構成部品は、電子制御ユニット（ＥＣＵ）と呼ばれる。
【０００３】
ＥＣＵは、一般的に、センサからの入力信号を、例えばＡ／Ｄ変換する入力インターフェースと、決められた論理に従ってディジタル入力信号を処理する論理演算部（マイクロコンピュータ）と、その処理結果を、アクチュエータ作動信号に変換する出力インターフェースとから構成される。
【０００４】
ＥＣＵがカバーする範囲は、エンジン制御だけではなく、ステアリング、トランスミッション、ブレーキなど多岐に亘り、最近では、５０個以上ものＥＣＵを搭載する自動車も珍しくない。このように多数のＥＣＵが自動車に搭載されると、開発段階で、複数のＥＣＵがきちんと適正に協働して動作するかどうかをテストするのが困難になってきている。
【０００５】
このようなテストにために従来行われている技法として、ＨＩＬＳ(Hardware In the Loop Simulation)がある。特に、自動車全体のＥＣＵをテストする環境は、フルビークルＨＩＬＳと呼ばれる。フルビークルＨＩＬＳにおいては、実験室内で、本物のＥＣＵが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ＥＣＵからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。
【０００６】
しかし、ＨＩＬＳは、専用のハードウェア装置を使い、それと本物のＥＣＵの間を物理的に配線しなくてはならないので、準備が大変である。また、別のＥＣＵに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のＥＣＵを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、ＨＩＬＳのエミュレーション用のハードウェア装置は、一般に、非常に高価である。
【０００７】
そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、ソフトウェアで構成する手法が存在する。この手法は、ＳＩＬＳ(Software In the Loop Simulation)と呼ばれ、ＥＣＵに搭載されるマイクロコンピュータ、入出力回路、制御のシナリオなどを全て、ソフトウェア・シミュレータで構成する技法である。これによれば、ＥＣＵのハードウェアが存在しなくても、テストを実行可能である。
【０００８】
ＥＣＵシミュレータをテストする際、クロックに従い動作させている間になんらかの異常な動作がみつかると、そこの点に戻ってテストを再開したい、という必要性がある。しかし、ＥＣＵシミュレータは、マイクロコンピュータを内蔵する動作をシミュレートするものであるため、内部状態の変数をもち、すなわち、ＥＣＵシミュレータの出力は、その入力信号だけからは決まらない。従って、ある状態に戻ってテストを再開するためには、その時点の内部状態の変数の値も復元する必要がある。
【０００９】
ところが、ＥＣＵシミュレータのプログラムは本来、内部状態をきちんと取り出せるように書かれているとは限らない。そこで、ＥＣＵシミュレータのプログラムのソースコードを人手で解析して、内部状態を切り離すようにソースコードを書き換える方法が考えられる。ここで、内部状態を切り離すとは、例えば、ＥＣＵシミュレータに割当てられたプライベート・メモリに、内部状態の変数の値を書き出すことにより、後で参照可能とする、などの処理をいう。
【００１０】
しかし、そのようなソースコードの解析を人手で行っていると、膨大な手間と時間がかかるだけでなく、ソースコードを不注意に書き換えて、動作しなくなる恐れもでてくる。
【００１１】
特開２００４−３１８５２３号公報は、デバイスドライバにおいて内部処理の実行状態を把握することを可能とするために、所定のデバイスを駆動する際に起動されるデバイスドライバであって、上記デバイスを駆動する際に、オペレーティングシステムに対して制御アプリケーションプログラミングインターフェース（ＡＰＩ）の呼び出しを行いつつ、同ＡＰＩに基づいた所定の機能を実行可能な実行モジュールと、上記オペレーティングシステムと上記実行モジュールとの間に介在し、同実行モジュールが呼び出しを行うＡＰＩを取得し、同取得したＡＰＩに関する所定の関連情報を出力可能であるとともに、上記取得したＡＰＩについて上記オペレーティングシステムに対する呼び出しを行い、上記機能を実行させるＡＰＩ制御モジュールとを具備することを開示する。
【００１２】
特開２００４−３１８５２３号公報の技術は、デバイスドライバなどのモジュールにおいて、内部処理の実行状態を知ることができるようにするが、内部状態を所定の状態に復元する技術は提供しない。
【００１３】
【特許文献１】特開２００４−３１８５２３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
この発明の目的は、ＥＣＵなどの組み込みプログラムの動作を効率的に検証することを可能ならしめる技術を提供することにある。
【００１５】
この発明の他の目的は、ＥＣＵなどの組み込みプログラムにおいて、内部状態の把握と、任意の内部状態への復元を可能ならしめる技術を提供することにある。
【課題を解決するための手段】
【００１６】
上記目的は、本発明に従い、次のような処理を行うことによって達成される。先ず、内部状態のメモリ領域を特定・抽出するために、ＥＣＵなどの組み込みプログラムの実行フローを解析して、コントロール・グラフを生成する。これによって、実行パスが得られる。
【００１７】
次に、実行パスについて、Def/Useのデータフロー解析を行う。Def/Useのデータフロー解析とは、定義(Def)より先に参照(Use)が行われる変数の全リストを得ることである。本発明によれば、そうして得られた変数の全リストが、内部状態を表現するメモリ領域であると見なされる。
【００１８】
こうして、得られた、内部状態を表現する変数のリストを用いて、入力用のラッパ(wrapper)と、出力用のラッパが生成され、それぞれが、解析された組み込みプログラムの前後に配置される。こうしてラッパを配置されたプログラムは、コンパイルあるいはアセンブルされて、バイナリの実行可能プログラムとされる。
【００１９】
入力用のラッパの内部状態を表現する変数に所定の値を入れることによって、所定の内部状態から、組み込みプログラムの動作を開始させることができる。この動作の結果、出力用のラッパがもつ変数に、内部状態を表現する変数のリストが格納される。
【発明の効果】
【００２０】
この発明によれば、もともと内部状態を取り出すことができないプログラムから、人手を介することなく自動的に、内部状態を取り出すことができるようにプログラムを変更することが可能となり、以って、プログラムのテストの際の再現性を高めることができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００２２】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）  ４、Ｃｏｒｅ（商標）  ２  ＤＵＯ、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。
【００２３】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システム、解析すべきＥＣＵシミュレーション・プログラムのソースコード、及び本発明に係る処理プログラムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ（商標）  Ｖｉｓｔａ、Ｗｉｎｄｏｗｓ  ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ  ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２４】
ハードディスク・ドライブ１０８にはまた、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などの任意のプログラム言語処理系を格納してもよい。このプログラム言語処理系は、本発明に係る処理プログラムを作成し、維持するために使用される。
【００２５】
ハードディスク・ドライブ１０８にはさらに、プログラム言語処理系でコンパイルするためのソースコードを書くためのテキスト・エディタ、及び、Ｅｃｌｉｐｓｅ（商標）などの開発環境を含んでいてもよい。
【００２６】
ハードディスク・ドライブ１０８にはさらに、図示しないが、好適には逆アセンブリ・プログラムと、逆コンパイル・プログラムが含まれる。これは、テストすべきＥＣＵシミュレーション・プログラムが、オブジェクトコードや実行可能なバイナリ形式でしか提供されていない場合に、一旦、ニーモニックからなるアセンブラ・ソースコードあるいは、Ｃなどの高級言語のソースコードに変更するために使用される。なお、逆アセンブリ・プログラムが利用する技術は、例えば、特開昭５９−７１５４６号公報などに記述されている。また、逆コンパイル・プログラムが利用する技術は、例えば、特開昭６４−５４５３７号公報、特開２００５−８５０５１号公報などに記述されている。本発明では、ごく一般的な逆アセンブリ・プログラムまたは、逆コンパイル・プログラムを使用することができ、そのための機能は、本発明にとって本質的ではないので、これ以上詳述しない。
【００２７】
キーボード１１０及びマウス１１２は、オペレーティング・システムまたは、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を起動したり、文字を打ち込んだりするために使用される。
【００２８】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、必要に応じて、本発明に係る処理結果を表示するために使用される。
【００２９】
次に、図２を参照して、本発明の処理の概念を説明する。図２において、プログラムコード２０２は、これには限定されないが、例えば、自動車の特定のＥＣＵをシミュレートするプログラムのソースコードである。なお、ソースコードが手に入らず、実行可能なバイナリプログラムしか入手ではない場合は、少なくとも逆アセンブラで、アセンブラ・コードに変換するか、または、逆コンパイラで、Ｃなどの高級言語のソースコードに変換して保存しておくものとする。入力２０４は、図示しないが、例えば、センサからの入力信号をシミュレートしたものであり、エンジンの温度などを計測する温度センサ、エンジンに吸入される圧力を推定するための圧力センサ、アクセスペダルの踏み量を測定するスロットル・ポジション・センサ、ステアリング舵角センサ、車高センサ、回転速度センサ、ノックセンサ、加速度センサ、流量センサ、酸素センサ、希薄空燃比センサなどである。
【００３０】
プログラムコード２０２に対応する実行可能プログラムをもつＥＣＵシミュレータは、入力信号２０４と、内部状態のパラメータまたは変数値２０６から、出力信号２０８を出力する。出力信号２０８は、エンジンのインジェクタ、トランスミッションのシフト・コントロール、ブレーキのバルブ制御、ドアロックなのアクチュエータをシミュレートするプログラムに入力される。
【００３１】
こうして出力すると、内部状態の変数値２０６は、変化している。従って、もし入力信号２０４と内部状態の変数値２０６を時系列的に保存すると、保存した値を、それぞれ入力信号２０４と内部状態の変数値２０６にセットすることによって、任意の状態に、ＥＣＵシミュレータを戻して再開させことができる。
【００３２】
しかし、一般的に、内部状態の変数値は、プログラムコード内に埋め込まれて、取り出すのは容易ではない。だから、内部状態の変数値を後での呼び出しのために保存したり、あるいは、内部状態の変数値をセットする、と言っても、任意のプログラムコードで、そのような処理が自明に可能である訳ではない。
【００３３】
そこで、本発明は、プログラムコード２０２のソースコードに前処理を施し、その前処理の結果取り出した変数で以って、入力用のラッパコード２１０と、出力用のラッパコード２１２を生成し、もとのプログラムコード２０２の入口と出口に、入力用のラッパコード２１０と、出力用のラッパコード２１２をそれぞれ配置する。このことは、本発明による処理プログラムによって自動的に行われる。このようなラッパコードの生成処理については、後で詳細に説明する。
【００３４】
このように入力用のラッパコード２１０と、出力用のラッパコード２１２が配置されると、プログラムコード２０２自体に改変を加えることなく、入力用のラッパコード２１０に含まれている内部状態の変数値に、内部状態の値２１４として値を供給することによって、プログラムコード２０２の内部状態の変数値２１６をセットすることができる。
【００３５】
図２に示されているように、実行可能プログラムを得るためにアセンブルまたはコンパイルされるのは、入力用のラッパコード２１０と、もとのプログラム・ソース・コード２０２と、出力用のラッパコード２１２の組み合わせである。このとき、コード２１０、２０２、及び２１２が、アセンブラ・ソース・コードの場合は、アセンブルが行われ、コード２１０、２０２、及び２１２が、Ｃのような高級言語のソース・コードであるなら、コンパイルが行われる。
【００３６】
また、プログラムコード２０２の内部状態の変数値２１６は、出力用のラッパコード２１２から、随時、内部状態の変数値２１８として取り出すことができる。こうして取り出された内部状態の変数値２１８は、後で自己参照するためにプライベート・メモリにストアしてもよく、あるいは、ハードディスク・ドライブ１０８の所定領域に書き出してもよい。
【００３７】
図３は、本発明の処理プログラムによる、処理の流れを示すブロック図である。図３で、ＥＣＵコード３０２は、ＥＣＵシミュレーション用のソースコードである。既述のように、もしオブジェクトコードまたは、バイナリの実行可能ファイルしかなければ、逆アセンブルまたは逆コンパイルして、ソースコードを用意し、ハードディスク・ドライブ１０８に保存しておく。すると、本発明の処理プログラムが、ハードディスク・ドライブ１０８から、それらのソースコードを読み取り、以下で説明する処理を行う。
【００３８】
本発明の処理プログラム自体も、ハードディスク・ドライブ１０８に保存され、キーボード１１０またはマウス１１２の操作により、オペレーティング・システムの動作で、主記憶１０６にロードされて、処理を行うように動作する。本発明の処理プログラムは、基本的に、テキストファイルからなるソースコードをスキャンして、変数を見つける処理を行うもので、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などの任意のプログラムで書くことができる。
【００３９】
次に、ブロック３０４は、ソースコードの実行フロー解析を行うように動作する。実行フロー解析の目的は、複数の制御が合流するところ、または、制御が複数に分岐するところでソースコードを区切った、ソースコードの部分（基本ブロック）に、ソースコードを分解することである。例えば、下記のようなＣ言語のコードがあったとき、
if ( condition )   // 基本ブロック１
{
// 処理１            基本ブロック２
・・・
//  処理１の終わり
} else             {
// 処理２            基本ブロック３
・・・
//  処理２の終わり
}
のように、分割する。
【００４０】
その結果、ソースコードをスキャンするための実行パス３０６が得られる。これには、分岐を含む、基本ブロックを巡る、ソースコードの実行パスが含まれる。
【００４１】
ブロック３０８は、実行パスに沿った内部状態変数解析を行う。内部状態変数解析とは、本発明では、次のように行われる。すなわち、Ｃ言語を例にとると、if、for、whileなどの分岐や判断ループ制御ステートメントを除くと、ステートメントは、定義ステートメントと、参照ステートメントに分けることができる。
【００４２】
定義ステートメントとは、変数に値を代入するステートメントであり、例えば、i = 0;  は、iを定義(Def)している。
【００４３】
一方、参照ステートメントとは、その変数を使って関数を呼び出したり、その変数の値を、他の変数に代入するステートメントである。例えば、i = j; は、jを使用(Use)している。ブロック３０８の基本的な機能は、定義なしで、あるいは定義される前に参照されている変数を見出すことである。このような変数を、ブロック３０８は、内部状態変数であるとみなす。
【００４４】
こうして、ブロック３０８の処理が完了すると、内部状態変数３１０が得られる。
【００４５】
ラッパ生成ブロック３１２は、内部状態変数３１０を用いて、図２に示す入力用ラッパと、出力用ラッパを生成し、もとのＥＣＵコード３０２と組み合わせて、ラッパ付のＥＣＵコード３１４が生成される。
【００４６】
次に、図３の機能ブロック図で示した構成の、処理フローチャートを、図４を参照して説明する。図４のステップ４０２では、ソースコードの実行フローへの変換が行われる。ステップ４０２で行われることをより詳しく既述すると、以下のとおりである。
【００４７】
先ず、ソースコードが複数の基本ブロックに分割される。基本ブロックとは、ソースコードを、複数の制御が合流するところ、または、制御が複数に分岐するところで分断した、各々の部分のことである。このような基本ブロックをノードとして、その分岐の制御の流れのリンクで接続すると、有向グラフ構造になる。これは特に、制御フローグラフとも呼ばれる。制御フローグラフは、始点ノードと終点ノードをもち、プログラムで実行され得るノードは全て、始点ノードからの有効エッジをもつ。基本ブロックのうち、exit()やreturnなどのステートメントを含む制御の末端ノードは全て、終点ノードへの有効エッジをもつ。
【００４８】
このようにステップ４０２で、ソースコードから実行フロー構造、あるいは制御フローグラフへ変換が行われると、ステップ４０４では、すべての実行フローをスキャンしたかどうかが判断される。ここで、実行フローというのは、制御フローグラフにおける、始点ノードから終点ノードに至る１つの経路である。ここの処理では結局、始点ノードから終点ノードに至る全てのパスを通ることになる。この場合、一般に知られているグラフ経路探索アルゴリズムを使用することができる。
【００４９】
ステップ４０６では、１つのパスにおいて、全ての行をスキャンしたかどうかが判断される。もしそうであるなら、ステップ４０８で、次のパス、すなわち実行フローに移って、ステップ４０４での判断を行う。
【００５０】
ステップ４１０では、次の行が調べられる。ここでは、ソースコードの、その行に含まれている変数が、DefなしでUseされているかが調べられる。このDefなし、という判断は、目下の実行フローの範囲だけことであって、他の実行フローでDefされているかどうかは関係ない。
【００５１】
そこで、ステップ４１２では、未定義変数があるかどうかが判断される。未定義変数とは、ここでは、DefなしでUseされていることを意味する。未定義変数がないと、処理は直ちにステップ４０６に戻る。未定義変数があると判断されると、ステップ４１４で、その変数が、未定義参照変数として登録される。ここで登録されるのは、変数の値ではなく、i, jなどの変数記号そのものである。その登録は、例えば、主記憶１０６に一旦格納してもよいし、ハードディスク・ドライブ１０８に一旦書き込んでもよい。
【００５２】
その後、処理はステップ４０６に戻り、そこで、１つの実行フローの全ての行がスキャンされたと判断されると、ステップ４０８で次の実行フローに移行することが試みられて、ステップ４０４でまだスキャンしていない実行フローがあると判断されると、処理は、ステップ４０６に移行する。
【００５３】
ステップ４０４で、全ての実行フローのスキャンが完了したと判断されると、処理はステップ４１６に進み、ここで、未定義参照変数として保存されている変数を用いて、ラッパコードを生成する。
【００５４】
ところで、実行フローのスキャンと、Use/Def解析は、データーフロー解析という技法を用いることによって、より効率的に実行することができるので、以下、それについて説明する。
【００５５】
その第１ステップは、各基本ブロックにおけるdefリストの計算である。具体的にはプログラム全体で使用される変数のリストを１ビットで表現し、各基本ブロックごとに定義される変数を１されないものを０としたビットベクタで表現する。
【００５６】
その第２ステップは、プログラム全体の到達可能なdefリストの計算である。すなわち、各基本ブロックでは、複数の入力がある場合には論理積（ＡＮＤ）してから，自身への入力とする。自身からの出力は、その入力と、自身で定義したdefリストの論理和（ＯＲ）をとり、後続の基本ブロックに渡す。実行していく順番は、制御フローグラフ上での深さ優先順序が効率的である。
【００５７】
第３ステップは、クロージャ解析アルゴリズムにより、到達可能なdefリストのクロージャを求めることである。そして、上記第２ステップを、全ての基本ブロックの出力defリストが変化しなくなるまで、繰り返す。ここで、クロージャとは、環境と結び付けられた値のことである。
【００５８】
第４ステップは、未定義変数の使用の発見である。すなわち、各基本ブロックの入力defリストが０として表現された変数が、useとして使用されているものを検出する。
【００５９】
なお、データフロー解析のより詳しい説明については、Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, "Compilers Principles, Technologies, and Tools", Addison-Wesley Publishing Company, 1986, p. 608-633などを参照されたい。
【００６０】
さて、例えば、元のＥＣＵシミュレーション・ソースコードが、関数 Func(x,y,z) であらわされるとする。また、未定義参照変数として、a, bが登録されていたとする。
【００６１】
すると、例えば、_Func(x,y,z,_a,_b)という関数が用意され、
_Func(x,y,z,_a,_b)
{
a = _a;
b = _b;
Func(x,y,z);
_a = a;
_b = b;
return;
}
【００６２】
_Func(x,y,z,_a,_b)
{
a = _a;
b = _b;
の部分のところを、入力用ラッパコードと呼び、
_a = a;
_b = b;
return;
}
の部分のところを、出力用ラッパコードと呼ぶ。
【００６３】
なお、 Func(x,y,z);  のところは、関数呼び出しではなく、インライン展開でもよい。このような関数_Func(x,y,z,_a,_b)を、_a,_bに適当な値を入れて呼び出すことにより、Func(x,y,z)の内部状態をセットすることができ、また、_Func(x,y,z,_a,_b)を呼び出した結果、_a,_bに、処理後の内部状態の値がセットされるので、必要に応じて、それらの値を別途保存するなど、利用可能である。
【００６４】
また、Ｃ＋＋など、特定の処理言語の仕様によっては、_Func(x,y,z,_a,_b)でなく、_Func(x,y,z,&_a,&_b)のように、参照演算子&をつけて関数に引数として与える必要があることもある。
【００６５】
以下、発明の理解を助けるために、より具体的に、下記のようなプログラム・ソースコードに従い、本発明の実施例を説明する。下記の例は、低レベルのアセンブラ・コードの擬似コードで既述されているが、この発明は、特定の言語に限定されず、Ｃ、Ｃ＋＋、Ｊａｖａなどの任意のコンピュータ言語で既述されたソースコードに適用可能であることを、この分野の当業者なら理解するであろう。
さて、下記のコードは、X = X + Y, Count = Count + 1を計算するものである。
reg1、reg2、reg3は、レジスタ変数であり、load()は、メモリ領域からレジスタにロードするコマンドであり、store()は、レジスタからメモリ領域にストアするコマンドである。
DWは、メモリ配列の宣言であり、Sum、Countは、メモリ配列のラベル名である。
また、accumulate(X,Y,Count):は、関数宣言のラベルである。
【００６６】
accumulate(X,Y,Count):  /* X:reg1, Y:reg2, Count:reg3 */
if reg3 < 0 goto init
body:  reg1 = load(Sum)
reg1 += reg2
store(Sum) = reg1
reg3 = load(Count)
reg3 += 1
store(Count) = reg3
return
init:  store(Sum) = 0
store(Count) = 0
goto body
DW     Sum
DW     Count
【００６７】
本発明の処理プログラムは、このソースコードをスキャンして、
"if reg3 < 0 goto init"  の判断分岐に従い、図５に示すように、３つの基本ブロックBB = 0, BB = 1, 及びBB = 2に、ソースコードを分割し、ソースコードの処理の流れに従い、図５に示すような制御フローグラフを形成する。実際は、この有向グラフをあらわすデータ構造として、主記憶１０６にロードされる。この処理は、図４のステップ４０２に対応する。
【００６８】
そこで、図５から見て取れるように、実行フローとしては、
BB = 0 → BB = 1  と、
BB = 0 → BB = 2 → BB = 1
という、２つがある。
【００６９】
以下、図６を参照して、Def/Use解析について説明する。
最初のaccumulate(X,Y,Count):では、３つのレジスタreg1、reg2、reg3を定義するので、
Def(reg1)
Def(ref2)
Def(reg3)
である。
【００７０】
BB = 0の基本ブロックでは、reg3に値が代入されているのでなく、単に参照されているので、
Use(reg3)
である。
【００７１】
BB = 1の基本ブロックでは、
reg1 = load(Sum)に対して、
Use(Sum)
Def(reg1)
reg1 += reg2に対して、
Use(reg1)
Use(reg2)
Def(reg1)
store(Sum) = reg1に対して、
Use(reg1)
def(Sum)
reg3 = load(Count)に対して、
Use(Count)
Def(reg3)
reg3 += 1に対して、
Use(reg3)
Def(reg3)
store(Count) = reg3に対して、
Use(reg3)
Def(Count)
【００７２】
BB = 2の基本ブロックでは、
store(Sum) = 0に対して、
Def(Sum)
store(Count) = 0に対して、
Def(Count)
【００７３】
すると、BB = 0 → BB = 2 → BB = 1という実行フローに対しては、どの変数も、必ずDefされた後、Useさていることが確認できる。
【００７４】
ところが、BB = 0 → BB = 1という実行フローに対しては、reg1 = load(Sum)についてのUse(Sum)をみると、その前に、Def(Sum)は存在しない。従って、図４のステップ４１２で、Sumは未定義変数として判断され、ステップ４１４で、未定義参照変数として登録される。
【００７５】
同様に、BB = 0 → BB = 1という実行フローにおいて、reg3 = load(Count)についてのUse(Count)をみると、その前に、Def(Count)は存在しない。従って、図４のステップ４１２で、Sumは未定義変数として判断され、ステップ４１４で、未定義参照変数として登録される。
【００７６】
こうして、SumとCountが、未定義参照変数として登録されると、図４のステップ４１６に関連して説明したように、もとのソースコードの前後にそれぞれ、下記のように、入力用ラッパコードと、出力用ラッパコードが付加される。
【００７７】
$$accumulate (X,Y,Count,_Sum,_Count)
store(Sum) = _Sum
store(Count) = _Count
call accumulate(X,Y,Count)
goto finalize
accumulate:
...
...
finalize:    _Sum = load(Sum)
_Count = load(Count)
return
【００７８】
すなわち、accumulate:から、finalize:の前までが、もとのソースコードであり、
$$accumulate (X,Y,Count,_Sum,_Count)
store(Sum) = _Sum
store(Count) = _Count
call accumulate(X,Y,Count)
goto finalize
が、入力用ラッパコードであり、
finalize:  _Sum = load(Sum)
_Count = load(Count)
return
が、出力用ラッパコードである。
【００７９】
すなわち、入力用ラッパコードは、もとの関数名accumulate(X,Y,Count)をもとに、
$$accumulate (X,Y,Count,_Sum,_Count)が生成され、入力用ラッパコード内で、
引数変数_Sumと、_Countがそれでれ、SumとCountにストアされる。そこで、もとのコードを、call accumulate(X,Y,Count)で呼ぶと、ストアされたSumとCountが、その内部で利用される。
【００８０】
一方、入力用ラッパコードで、call accumulate(X,Y,Count)が処理から戻ってくると、goto finalizeで、出力用ラッパコードの先頭に移る。そこで、出力用ラッパコード内で、SumとCountが、_Sumと_Countにそれぞれ、ロードされる。こうして、内部状態の変数_Sumと_Countが、ソースコードのプログラムの外で利用可能になる。
【００８１】
実際は、このように変換されたソースコードが、コンパイルまたはアセンブルされて、実行可能なプログラムとして使用される。
【００８２】
なお、上記の例は、アセンブラ的な擬似コードをもとに説明したが、Def/Useの判定は、どのようなプログラミング言語でも可能であるから、本発明は、特定のプログラミング言語に限定されるものではなく、任意のプログラミング言語に適用可能であることが理解されよう。
【００８３】
また、ＥＣＵシミュレーション用プログラムのみならず、任意のプログラムに本発明を適用することが可能である。
【図面の簡単な説明】
【００８４】
【図１】ハードウェア構成のブロック図である。
【図２】ラッパ付きソースファイル処理の概要を示すブロック図である。
【図３】ラッパ作成処理の論理ブロック図である。
【図４】ラッパ作成処理のフローチャートを示す図である。
【図５】実行フロー解析の例を示す図である。
【図６】Def/Use解析の例を示す図である。
【図１】
0005159408.tif 000002
【図２】
0005159408.tif 000003
【図３】
0005159408.tif 000004
【図４】
0005159408.tif 000005
【図５】
0005159408.tif 000006
【図６】
0005159408.tif 000007