(57)【特許請求の範囲】
【請求項１】
原始プログラム（ソースコード）の翻訳（コンパイル）時に、
各代入文について、当該代入文によって代入される値が再生可能であるか否かを判定し、再生可能である場合は、前記代入される値を再計算するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記代入される値をログ情報として出力した後に代入処理を実行するコードを、順方向プログラムのコードとして生成し、前記代入される値を前記ログ情報から読み取って前記代入される値を復元するコードを、逆方向プログラムのコードとして生成し、
各関数について、破棄される変数値が再生可能である場合は、当該変数値を再生するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記変数値をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記変数値を前記ログ情報から読み取って前記変数値を復元するコードを、逆方向プログラムのコードとして生成し、
各分岐処理について、分岐先を示す情報をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記分岐先を示す情報を前記ログ情報から読み取って分岐処理を実行するコードを、逆方向プログラムのコードとして生成することによって、
翻訳結果としてログ情報を生成する順方向プログラムと前記ログ情報の読み取りに基づいて実行される逆方向プログラムの２種類のプログラムの生成を行い、
順方向プログラムの実行時に生成されたログ情報を入力として逆方向プログラムを実行することで順方向プログラムの過去の状態を復元する
ことを特徴とするソフトウエア障害解析方法。
【請求項２】
原始プログラム（ソースコード）の翻訳（コンパイル）時に、
各代入文について、当該代入文によって代入される値が再生可能であるか否かを判定し、再生可能である場合は、前記代入される値を再計算するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記代入される値をログ情報として出力した後に代入処理を実行するコードを、順方向プログラムのコードとして生成し、前記代入される値を前記ログ情報から読み取って前記代入される値を復元するコードを、逆方向プログラムのコードとして生成し、
各関数について、破棄される変数値が再生可能である場合は、当該変数値を再生するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記変数値をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記変数値を前記ログ情報から読み取って前記変数値を復元するコードを、逆方向プログラムのコードとして生成し、
各分岐処理について、分岐先を示す情報をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記分岐先を示す情報を前記ログ情報から読み取って分岐処理を実行するコードを、逆方向プログラムのコードとして生成することによって、
翻訳結果としてログ情報を生成する順方向プログラムと前記ログ情報の読み取りに基づいて実行される逆方向プログラムの２種類のプログラムの生成を行うコンパイラと、
順方向プログラムの実行時に生成されたログ情報を入力として逆方向プログラムを実行することで順方向プログラムの過去の状態を復元する障害解析手段（デバッガ）と
を備えたことを特徴とするソフトウエア障害解析装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ソフトウェア障害解析（デバッグ）方法及び装置に関し、特に、原始プログラム（ソースコード）を計算機の命令語へ翻訳（コンパイル）する方法を工夫することによりプログラムを逆向きに実行できるようにして障害が発生した時点より前の状態を再現できるようにすることで障害解析を行いやすくするものである。
【０００２】
【従来の技術】
ソフトウェアの障害解析では、何らかの異常（障害）を検出した時点でプログラムの動作をストップさせ、その時点のメモリの状態を詳しく調べることで障害の原因を推定する方法が広く使われている。
【０００３】
しかし、この方法では障害が検出された時点での情報しか得られないため、それ以前にどのような経過をたどって障害に至ったのかについては正確な情報が得られないという問題がある。従来技術では、この問題を解決するため以下のような技術が知られている。
【０００４】
（１）変数値やプログラムの状態を表示またはファイルに保存する処理をプログラムに埋め込み、実行中の中間結果を記録に残すことで障害の原因を推定する方法。しかし、表示処理や記録処理の埋め込みはプログラムの設計時に行う必要があり、どの情報を記録すればよいのか等の判断も設計時に行う必要がある。また、プログラムの状態を正確に知るためには記録すべき情報量が多くなるという欠点をもつ。
【０００５】
（２）逆命令ログに基づく方法。一般には、アプリケーション・プログラムのユーザー・インタフェース部分でＵＮＤＯ処理（取り消し処理）を実現するために用いられる方法で、実行プログラムの処理を行うたびに、その処理を打ち消すような処理を行う命令列（逆命令）を記録に残しておく方法である。この逆命令の実行によって、プログラムが停止した時点より前の状態を再現させ、障害に至った原因を推定することができる。この方法は、多段階の取り消しを容易に実現できるという特徴を持つ。
【０００６】
【発明が解決しようとする課題】
プログラムの動作の過程を調べるためには、障害が起こった時点から過去の状態へ溯って調べていく方法が有効だが、これを逆命令ログに基づく方法を用いて実現すると、ログに記録すべき情報量が多くなり長時間の記録が行えないという問題が発生する。これは、従来の技術では、命令の種類と、命令が操作するメモリ・アドレスとデータのサイズ、及び、状態を回復するためのデータなど、処理に必要な全ての情報がログの中に含まれているためである。
【０００７】
この発明は上述した点に鑑みてなされたもので、上述した逆命令に基づく方法を改良し、命令の種類の情報と、命令が操作するメモリのアドレス、およびデータ・サイズの情報を、逆方向プログラムの形でログから分離することで、ログの記録に必要なメモリの量を削減し、同一メモリ量で逆方向実行が可能な範囲を拡大することができるソフトウエア障害解析方法及び装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
この発明に係るソフトウエア障害解析方法は、原始プログラム（ソースコード）の翻訳（コンパイル）時に、各代入文について、当該代入文によって代入される値が再生可能であるか否かを判定し、再生可能である場合は、前記代入される値を再計算するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記代入される値をログ情報として出力した後に代入処理を実行するコードを、順方向プログラムのコードとして生成し、前記代入される値を前記ログ情報から読み取って前記代入される値を復元するコードを、逆方向プログラムのコードとして生成し、各関数について、破棄される変数値が再生可能である場合は、当該変数値を再生するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記変数値をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記変数値を前記ログ情報から読み取って前記変数値を復元するコードを、逆方向プログラムのコードとして生成し、各分岐処理について、分岐先を示す情報をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記分岐先を示す情報を前記ログ情報から読み取って分岐処理を実行するコードを、逆方向プログラムのコードとして生成することによって、翻訳結果として生成されるログ情報が書き込まれる順方向プログラムと前記ログ情報の読み取りに基づいて実行される逆方向プログラムの２種類のプログラムの生成を行い、順方向プログラムの実行時に生成されたログ情報を入力として逆方向プログラムを実行することで順方向プログラムの過去の状態を復元することを特徴とするものである。
【０００９】
また、この発明に係るソフトウエア障害解析装置は、原始プログラム（ソースコード）の翻訳（コンパイル）時に、各代入文について、当該代入文によって代入される値が再生可能であるか否かを判定し、再生可能である場合は、前記代入される値を再計算するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記代入される値をログ情報として出力した後に代入処理を実行するコードを、順方向プログラムのコードとして生成し、前記代入される値を前記ログ情報から読み取って前記代入される値を復元するコードを、逆方向プログラムのコードとして生成し、各関数について、破棄される変数値が再生可能である場合は、当該変数値を再生するコードを逆方向プログラムのコードとして生成し、再生不可能である場合は、前記変数値をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記変数値を前記ログ情報から読み取って前記変数値を復元するコードを、逆方向プログラムのコードとして生成し、各分岐処理について、分岐先を示す情報をログ情報として出力するコードを、順方向プログラムのコードとして生成し、前記分岐先を示す情報を前記ログ情報から読み取って分岐処理を実行するコードを、逆方向プログラムのコードとして生成することによって、翻訳結果として生成されるログ情報が書き込まれる順方向プログラムと前記ログ情報の読み取りに基づいて実行される逆方向プログラムの２種類のプログラムの生成を行うコンパイラと、順方向プログラムの実行時に生成されたログ情報を入力として逆方向プログラムを実行することで順方向プログラムの過去の状態を復元する障害解析手段（デバッガ）とを備えたことを特徴とするものである。
【００１０】
【発明の実施の形態】
この発明では、以下のような特徴をもつプログラムのコンパイル手段（コンパイラ）と、障害解析手段（デバッガ）を用いることで、上記の課題を解決する。
【００１１】
この発明のコンパイラは、ソースコードをプログラムに翻訳する際に、通常のプログラムと同じ順序で実行する「順方向プログラム」と、逆の順序で実行する「逆方向プログラム」を生成する。逆方向プログラムは、それを実行することで順方向プログラムの動作結果を打ち消すように構成される。このような２つのプログラムを生成するためには、プログラムの動作においてメモリの内容が書き換わる個所と、プログラムの流れ（制御フロー）が変更される個所に対して特別な処理を行う必要がある。
【００１２】
まず、メモリの内容が書きかえられる個所に対する処理を説明する。メモリ内容の書きかえには、（１）未初期化メモリを初期設定する場合、（２）初期化済みメモリの内容を上書きする場合、（３）初期化済みメモリを開放する場合の３種類がある。
【００１３】
未初期化メモリを初期化する場合は、逆方向プログラムとしてメモリの内容が未初期化状態に戻ったことを障害解析手段（デバッガ）に対して伝達する逆方向プログラムを出力する。これによって、順方向プログラムでは未初期化メモリが初期化される過程が、逆方向プログラムでは初期化済みメモリが未初期化状態へ戻る過程として再現されることになる。
【００１４】
初期化済みメモリの内容を上書きする場合は、上書きされる前のメモリ内容を何らかの方法で保存しておき、逆方向プログラム側で保存されていた値を復元することによって、メモリが上書きされる前の状態を復元する。この時、上書きされる前のメモリの内容を復元するには、以下に示す３通りの方法を使用する。
【００１５】
１番目の方法は、失われるデータを順方向プログラム側でログ用のメモリに保存しておき、逆方向プログラム側でそれを取り出して復元する方法である。この方法は従来技術である逆命令ログ法とよく似ているが、逆命令ログ法ではログ情報として、逆命令、アドレス、サイズなどの情報がログに記録されるのに対し、この発明の方法では逆方向プログラムを実行することでこれらの情報が得られるため、ログに記録する必要がないという特徴がある。
【００１６】
２番目の方法は、処理の内容がもともと可逆性のある演算である場合に、その可逆性を利用して値を復元する方法である。たとえば整数の値を１だけ増やす演算（インクリメント演算）は可逆性のある演算であり、これは値を１だけ減らす演算（デクリメント演算）を行うことによって、演算が行われる前の状態を復元することができる。したがって、順方向プログラム側でインクリメント演算を行う個所に対しては、逆方向プログラム側でデクリメント演算を行うことで、過去の状態を復元することができる。
【００１７】
３番目の方法は、メモリの上書きによって失われるデータを再度計算することによってデータを再生する方法である。失われたデータを計算するときに使用したデータが、まだ他の変数やログ領域の中に残っている場合に使用する。たとえば変数Ａの値が変数Ｂと変数Ｃの和であるとする。このとき、変数Ａの値が上書きによって失われても、変数Ｂと変数Ｃの値がまだ残っているならば、ＢとＣの和をもう一度計算することによって失われたデータを復元することができる。
【００１８】
次に、メモリ開放の場合について説明する。メモリの開放は、メモリが保持していたデータが失われるという点において本質的にメモリの上書きと同一である。そのため、メモリ上書きの場合と同じ手法を使用することでデータを再生することができる。ただし、メモリの開放は可逆性のある演算ではないので、失われるデータをログにとる方法と、再計算を行うことによってデータを再生する方法の２つのみが使用できる。
【００１９】
次に、制御の流れが変更される個所に対しての処理を説明する。制御の流れの変更に対しては、逆方向プログラムの制御の流れが、順方向プログラムの制御の流れと逆になるように構成する。制御の流れの変更には、条件分岐、無条件分岐、繰り返し（ループ）、サブルーチン呼び出し、割り込みの５つの種類がある。
【００２０】
順方向プログラムで条件分岐を行う処理は、逆方向プログラムでも条件分岐を行う処理となる。逆方向プログラムでは条件分岐の選択肢（経路）のうち、どれが選択されたかを再現する必要があるため、順方向プログラム側で選択結果を記録しておき、逆方向プログラムでその情報を元に条件分岐の選択を再現する。選択結果を記録する方法には、メモリの上書きによって失われる値を復元するのに使用したのと同じ方法を使う。
【００２１】
順方向プログラムで無条件分岐を行う個所に対しては、逆方向プログラム側では条件分岐を行うプログラムを生成する。これは、無条件分岐では複数の分岐が１つの飛び先（飛び先ラベル）に向かってジャンプする場合があるためで、逆方向プログラム側で無条件分岐を逆向きにたどるためには、どこから飛んできたのかを選択する必要があるためである。これに伴って、順方向プログラム側の無条件分岐を行う個所にも、どの場所からジャンプを行ったのかを記録する処理が必要になる。
【００２２】
順方向プログラムで繰り返し処理（ループ）を行う個所に対しては、逆方向プログラム側にもループの処理を生成する。逆方向プログラムの実行の際にはループがどれくらいの回数だけ回ったのかを再現する必要があるため、順方向プログラムの実行時にループの実行回数に関する情報を何らかの手段で記録しておき、逆プログラム側でそれを取り出して、順方向プログラムと同じ回数だけループするように構成する。
【００２３】
順方向プログラムでサブルーチン呼び出しを行う処理は、逆方向プログラムでも対応する逆方向プログラム内のサブルーチン呼び出しを行う処理となる。これについては特に特別な処理は必要ない。
【００２４】
割り込みに対しては特別な処理が必要になる。割り込みはいつ発生するのかあらかじめ予測できないため、いつ、どこで発生したのかを記録に残す必要がある。これには割り込み発生ログを使用する。割り込み発生ログは通常の逆方向実行用のログとは別の領域に保存する。また、割り込み発生ログを記録する処理は割り込みによって実行されるプログラム（割り込みハンドラ）の中に埋め込んでおく。
【００２５】
割り込み時点を表すデータには、その時点でのログ領域の先頭を表すカウンタ（ポインタ）と、割り込みが発生したプログラム上のアドレスのペアを用いる。このペアが割り込み時点を一意に表すようにするためには、ログがまったく出力されないようなループ処理やサブルーチン呼び出しがあってはならないため、このようなループ処理やサブルーチン呼び出しの個所に、ダミーのログ処理を入れておく。
【００２６】
どちらの場合でも、逆方向実行時に、割り込み発生ログが示す個所へ達したら、逆方向プログラム側の対応する割り込み処理が呼び出される必要がある。この呼び出し処理は障害解析手段（デバッガ）が行う。
【００２７】
次に、障害解析手段（デバッガ）の動作について説明する。障害解析手段は、まず順方向プログラムが停止している個所を求め、コンパイラが生成した順方向プログラムと逆方向プログラムの対応関係を表す情報を用いて、停止個所に対応する逆方向プログラムの位置を求め、その位置から逆方向プログラムを実行していくことによって順方向プログラムの過去の状態を復元する。
【００２８】
状態をどこまで復元するのかはソースコード上の位置をユーザーが指示することによって行う。ソースコードと順方向プログラムの対応関係、および、順方向プログラムと逆方向プログラムの対応関係を用いることで、逆方向プログラム上の位置が求められるので、その個所まで逆方向プログラムを実行すれば、指定された時点まで復元された状態となる。
【００２９】
以下、図示される具体的な実施の形態について説明する。
図１に、本実施の形態における障害解析手段（デバッガ）が動作している時のハードウェア構成と、そのメモリ内のソフトウェア構成を示す。計算機本体（０１０１）には、中央処理装置（プロセッサ）（０１０２）と、主記憶（メモリ）（０１０３）が含まれている。この主記憶（０１０３）上には翻訳手段（コンパイラ）が作成した順方向プログラム（０１０４）と、逆方向プログラム（０１０５）、および障害解析手段（デバッガ）（０１０６）のソフトウェアが含まれている。
【００３０】
順方向プログラムと、逆方向プログラムは、一つのデータ領域（０１０７）を共有し、この領域を使用して計算を行う。また、順方向プログラムの実行によって生成されたログ情報はログ領域（０１０８）に書き込まれ、逆方向プログラムの実行時に読み取られる。また、割り込みに関するログ（０１０９）は通常のログ領域とは別に取られる。
【００３１】
順方向プログラムと逆方向プログラムの切り替えや、その他の障害解析に関わる処理は、障害解析手段のソフトウェア（デバッガ）が行う。このソフトウェアの働きによって、プロセッサが順方向と逆方向のどちらのプログラムに対して割り当てられるかがコントロールされる。障害解析を行う使用者（ユーザ）は制御端末（０１１０）経由でこのデバッガを操作し、順方向プログラムまたは逆方向プログラムの実行、およびメモリ中のデータの表示や修正などの操作を行う。
【００３２】
次に、図２に、コンパイラ（翻訳手段）内部のブロック構成とデータ・フローを示す。コンパイラ（０２０２）は、ソース・プログラム（０２０１）をソース読み込み部（０２０３）で読み込み、字句解析部（０２０４）で文字列から記号を抽出し、構文解析部（０２０５）で文法の解析を行って中間解析木と呼ばれるデータ構造を作成する。この中間解析木に含まれる無駄な部分を構文木最適化部（０２０６）で取り除いた後、順方向コード生成部（０２０７）と、逆方向コード生成部（０２０８）で計算機の命令コードを生成する。
【００３３】
この部分がこの発明の特徴的な部分である。通常のコンパイラでは一つのコードのみを生成するのに対し、この発明のコンパイラでは順方向実行用のコードと、逆方向実行用の２つのコードを生成する。この部分の詳細については後で詳しく述べる。
【００３４】
次に、コード生成処理で作られた計算機の命令コードに対して再度、最適化が行われる。これは計算機毎の特徴を生かした最適化を行うためである。そして、最後にコード出力部（０２１０）と対応関係テーブル生成部（０２１１）で、コンパイル結果のファイル（実行プログラム）（０２１２）に、順方向プログラム（０２１３）と、逆方向プログラム（０２１４）と、原始プログラム（ソースコード）と各プログラム間の対応関係を表す対応関係テーブル（０２１５）が生成される。
【００３５】
次に、コンパイラが内部で使用するデータ構造を図３に示す。このデータ構造は、メモリの上書きによってデータが失われる場合に、上書きされる前の値をログに残す必要があるものなのか、それとも他の変数から再計算して求められるものなのかを判定するのに使用する。
【００３６】
データ構造全体は、再生情報テーブル（０３０１）を中心に構成される。このテーブルは、変数または代入可能なメモリ領域（これを総称して左辺値と呼ぶ）に関する情報と、左辺値を参照する式（左辺式）に関する情報を示す再生情報（０３０２）が含まれている。また、再生情報は次々とテーブルに追加される形で登録されていくため、テーブルがどこまで使用されたかを示すのにテーブル先頭位置を示すポインタ（０３０３）を使用する。
【００３７】
再生情報は、個々の左辺値を識別するために使用する左辺式（０３０４）と、その左辺値がポインタ経由で書き換わる可能性（エリアシング可能性）があるかどうかを示す真偽値（０３０５）、その左辺値を参照するための式（参照式）（０３０６）、参照式を計算するために必要になる他の左辺式のリスト（参照依存先）（０３０７）、左辺値が失われたときに再計算する方法を示す再生式（０３０８）、再生式を計算するために必要になる他の左辺式のリスト（再生依存先）（０３０９）の合計６個の要素から構成される。
【００３８】
参照式と再生式は、中間解析木の形で式の情報を保持する（０３１１，０３１２）。一つの中間解析木には再帰的に複数の左辺式が含まれていて、それらの部分左辺式に関する再生情報もテーブルの中に確保される。どの部分左辺式がテーブルのどこに割り当てられたかを示すため、参照依存先リスト（０３１３）と、再生依存先リスト（０３１４）を使用する。依存先がテーブルのどの位置にあるかを示すのには、相対的な位置関係（例えばテーブルの１０個前にある等）を表す数値を用いる。
【００３９】
また、再生情報の１番目の要素の左辺式と、参照依存先リスト（０３１３）に含まれる左辺式、および再生依存先リストに含まれる左辺式については、再生情報の検索に使用するため中間解析木の形式ではなく文字列の式で表現する。
【００４０】
次に、このデータ構造を使用して順方向プログラムと逆方向プログラムのコード生成を行う手順について説明する。
まず、代入文をコード生成する場合の処理手順を図４に示す。この手順では、代入先を表す式と、代入する値を計算する式の２つのデータを引数として受け取る（Ｓ０４０１）。次に、ポインタを保持する変数がエリアシング可能であるときに必要になる特別な処理を行うための手順（Ｓ０４０２）を呼び出す。
【００４１】
次に、代入先の左辺式に一致する再生情報を再生情報テーブルから検索する。この時、左辺式が一致する再生情報が複数ある場合は、その中で最後に登録された再生情報を選択する。再生情報には、代入先のデータが失われた時に、それが再計算によって再生可能かどうかを判定できるデータが含まれているので、後述する図５に示す再生可能性の判定手順を用いて再生可能であるかどうかを判定する（Ｓ０４０４）。
【００４２】
もし、再生可能であると判定された場合は、順方向プログラムに対しては通常の代入処理を行うコードを生成する。また、逆方向プログラムに対しては再計算によって失われた値を再生し、それを代入先の左辺値に書き戻す処理を生成する（Ｓ０４０５）。また、再計算処理の生成には後述する図７に示す再生コードの生成手順を使用する（なお、図４のフローチャートでは、順方向プログラムに対するコード生成には「順：」、逆方向プログラムに対するコード生成には「逆：」と表記する）。
【００４３】
次に、再生情報の参照式と参照依存先に、再生式と再生依存先をコピーする（Ｓ０４０６）。これは、代入によって失われた値を参照する時には、再生式を使用して参照する必要があることを表す。
【００４４】
もし、代入先の左辺式が再生可能ではない場合は、順方向プログラム側に代入前にデータをログに保存する＿ＳＡＶＥ処理と、その後に通常の代入を行う代入処理を生成する。また、逆方向プログラムに対してはログからデータを読み出して代入先に書き戻す＿ＲＥＳＴＯＲＥ処理を生成する（Ｓ０４０７）。＿ＳＡＶＥ処理と＿ＲＥＳＴＯＲＥ処理の動作については図２０と図２１に示す。また、＿ＳＡＶＥ処理が何個生成されたかを表すログ生成個数カウンタをインクリメントしておく（Ｓ０４０８）。
【００４５】
次に、再生情報の参照式を、ログからデータを取り出す＿ＰＥＥＫ式に置き換える（Ｓ０４０９）。＿ＰＥＥＫ式にはログのどこからデータを取り出すかを指示する引数を与える必要があるが、その値には現在のログ生成個数カウンタの値を与える。この値は仮のもので、後で参照式が実際に使用されるときに修正される。また、参照依存先は空にする。＿ＰＥＥＫ式の動作については図２２に示す。
【００４６】
次に、新たに書き込まれた値に関する再生情報を登録する（Ｓ０４１０）。この登録は新しい再生情報を追加していく形で行うため、同一の左辺式に対する代入が複数箇所ある場合は複数の再生情報が登録されることになる。これは、左辺値の過去の状態を表す情報と、最新の状態を表す情報が、すべて記録に残るようにするためである。
【００４７】
再生情報のそれぞれの要素は次のように設定する。
（１）左辺式は登録する左辺式を文字列にしたものを設定する。
（２）エリアシング可能かどうかの真偽値には、ローカル変数と値渡しの引数に対しては偽、それ以外の左辺式については真を設定する。
（３）参照式に対しては左辺式の中間解析木をそのまま設定する。
（４）参照依存先については、参照式の部分左辺式をすべて取り出して一覧の形にし、それらを再生情報テーブルから検索して相対的な位置関係の情報を設定する。
（５）再生式には代入処理の右辺の式（右辺式）を設定する。これは最後に行われた代入がどのように行われたかを記録するためである。
（６）再生依存先については、参照依存先と同じように右辺式のすべての部分左辺式を取り出したリストを作成して設定する。
【００４８】
次に、再生可能性の判定手順を図５に示す。この手順は、判定対象の左辺式に関する再生情報を受け取り（Ｓ０５０１）、受け取った再生情報の再生式が空である場合は、再生不可能であることを表しているので偽（再生不能）であると判定して終了する（Ｓ０５０２，Ｓ０５０３）。逆に、再生式がある場合は、再生式の計算に必要になる依存先がすべて参照可能であるかどうかを検査する（Ｓ０５０４，Ｓ０５０６，Ｓ０５０７）。もし、すべての依存先が参照可能である場合は真（再現可能）であると判定して終了する（Ｓ０５０５）。逆に、一つでも参照不可能な依存先がある場合は、偽（再生不能）であると判定して終了する（Ｓ０５０８）。
【００４９】
依存先が参照可能であるかどうかは、図６に示す参照可能性の判定手順を使用する。この手順は、再生情報として渡された左辺式の参照依存先を再帰的にすべてたどり（Ｓ０６０１，Ｓ０６０２，Ｓ０６０３，Ｓ０６０４，Ｓ０６０６，Ｓ０６０７）、それら全てが参照可能である場合に真（参照可能）と判定する（Ｓ０６０５）。もし、一つでも参照不可能なものが見つかれば偽（参照不能）と判定する（Ｓ０６０９）。また、一度参照不能になったデータは、後から参照可能な状態に戻ることはないので、参照不能と判定された左辺式の参照式を空にしておくことで次回の判定が高速にできるようにしておく（Ｓ０６０８）。
【００５０】
次に、再生コード（再計算をすることで失われたデータを復元するプログラム・コード）を生成する処理手順を図７に示す。再生コードの生成では、再生依存先のすべての左辺値を参照する処理を生成し（Ｓ０７０１，Ｓ０７０２，Ｓ０７０３）、それらによって参照されたデータを用いて再生式を計算する処理を生成する（Ｓ０７０５）。ただし、再生式に＿ＰＥＥＫ式が含まれている場合は、現在のログ生成個数カウンタの値を＿ＰＥＥＫ式の引数から引いた値を計算し、その値で＿ＰＥＥＫ式の引数を置き換えた式を作って再計算を行うコードを生成する（Ｓ０７０６，Ｓ０７０７）。これは、実際に参照する時に参照先のログの位置がどれくらいの深さの所にあるのかを計算するためである。
【００５１】
また、参照コードの生成手順を図８に示す。これは、計算と検査の対象が再生式と再生依存先ではなく、参照式と参照依存先である点を除けば、図７に示す再生コードの生成手順と同じものである。すなわち、参照コードの生成では、参照依存先のすべての左辺値を参照する処理を生成し（Ｓ０８０１，Ｓ０８０２，Ｓ０８０３）、それらによって参照されたデータを用いて参照式を計算する処理を生成する（Ｓ０８０５）。ただし、参照式に＿ＰＥＥＫ式が含まれている場合は、現在のログ生成個数カウンタの値を＿ＰＥＥＫ式の引数から引いた値を計算し、その値で＿ＰＥＥＫ式の引数を置き換えた式を作って再計算を行うコードを生成する（Ｓ０８０６，Ｓ０８０７）。。
【００５２】
次に、自己破壊代入回避処理について説明する。自己破壊代入は、ポインタ経由で値を書き込む時にポインタ自身が失われるような代入で、代入先の左辺式がポインタ経由の左辺式で、かつポインタを保持する左辺値がエリアシング可能な場合にのみ発生する。このような代入に対しては代入よってポインタ値が失われる前にポインタを保存しておく必要がある。
【００５３】
図９に、自己破壊代入の恐れがある部分に対してポインタを保存する処理を生成する手順を示す。まず、代入先の左辺式がポインタ経由での代入かどうかを判定し（Ｓ０９０２）、かつポインタを保持する変数の再生情報を参照してエリアシング可能であるかを判定する（Ｓ０９０３）。この場合は、自己破壊代入が起きる可能性があるためポインタを保存する必要が生じる。
【００５４】
しかし、このようなポインタがポインタ自身を指しているという状態は多くのプログラムでは発生しないため、コンパイラに対するオプション指令によって、回避処理を行わないように指示できるようにしておけば、大部分のプログラムでオーバーヘッドを回避することができる。図９のステップ（Ｓ０９０４）はこの回避処理を生成するかどうかを判定する部分で、ユーザーが回避処理を生成すると選択した場合のみポインタの保存処理と再現処理を生成する（Ｓ０９０５）。
【００５５】
次に、代入を含む数式全体のコード生成手順を図１０に示す。図４から図９までの代入処理に関するコード生成手順は、図１０に示した式全体のコード生成手順から呼び出されるようになっている。
【００５６】
式全体のコード生成では、まず、最初に式全体を部分左辺式に分解し、それらが再生情報テーブルに登録されていない場合は、新たに登録する処理を行う（Ｓ１００２）。この時、図４に示す再生情報の登録処理（Ｓ０４１０）と同様に、再生情報内部の各情報を初期化しておく。ただし、この場合は、右辺式に相当するものは無いため、再生式と再生依存先は空の状態で生成する。
【００５７】
次に、式の中に左辺式のアドレスを取得する演算が含まれているかどうかを判定する（Ｓ１００３）。左辺式のアドレスが取得された場合、その左辺式はエリアシング可能になるため、再生情報にエリアシング可能であることを記録する。
【００５８】
次に、式が関数呼び出しを含んでいるかどうかを判定し（Ｓ１００５）、関数呼び出しが含まれている場合は、関数の帰り値を保持するローカル変数を追加して、関数呼び出しの部分を式から分離し（Ｓ１００６）、分離した関数呼び出しが式の計算の前に行われるようにする（Ｓ１００７）。これは、式の中から代入以外の副作用を取り除くためである。関数呼び出しのコード生成手順については後述する図１１に示す。
【００５９】
次に、式が可逆演算のパターンに一致しているかどうかを判定する（Ｓ１００８）。整数の加減算と符号反転、ビット値の排他的論理和（ＸＯＲ）とビット反転などの計算は、ログを使用しなくても計算結果から計算前の値を正確に再現することができるため、これらの演算に対して、あらかじめ用意しておいた変換パターンに基づいて順方向プログラムと逆方向プログラムを生成する（Ｓ１０１１）。この時、可逆パターン以外の部分についてはあらかじめ式を分離しておき（Ｓ１００９）、可逆パターン以外の式については、式のコード生成手順を再帰的に呼び出すことでコード生成を行う（Ｓ１０１０）。
【００６０】
次に、式が代入演算を含むかどうかを判定し（Ｓ１０１２）、代入演算が含まれている場合は、代入先（左辺式）と代入値を求める式（右辺式）に分離し（Ｓ１０１３）、左辺式と右辺式のペアを代入処理のコード生成手順（図４から図９）を呼び出すことで、代入に関するコードを生成させる（Ｓ１０１４）。
【００６１】
もし、式が可逆演算パターンに一致せず、代入演算でもない場合は、通常の数値計算であるため、通常のコンパイラが行うのと同じように、計算を行う処理を生成する（Ｓ１０１５）。
【００６２】
次に、関数呼び出しの手順を図１１に示す。関数呼び出しでは、まず、最初に実引数を評価する処理を生成しておく（Ｓ１１０２）。ただし、これは順方向プログラムの場合のみで、逆方向プログラムは引数の評価を必要としない。これは順方向プログラムが引数から結果を求めるのに対し、逆方向プログラムは結果から元データへと遡っていくためである。ただし、関数に与えるデータの量については、順方向プログラムと逆方向プログラムを一致させておく。これは、スタックのメモリ・レイアウトが順方向と逆方向で同じになるようにするためである。
【００６３】
引数を評価するコードの生成が終わったら、呼び出される関数が「副作用なし」と分類される関数に属しているかどうかを判定する（Ｓ１１０３）。これは、ＳＩＮやＣＯＳなどの、まったく副作用を持たない数学関数に対しては逆方向プログラムを生成する必要がないためである。もし、副作用のない関数であった場合は、順方向プログラム側だけに関数呼び出しのコードを生成しておく（Ｓ１１０４）。
【００６４】
逆に、「副作用なし」と登録されていない関数に対しては、順方向プログラム用の関数（関数名の先頭に＿Ｆ＿が付く）と、逆方向プログラム用の関数（関数名の先頭に＿Ｂ＿が付く）が生成されているはずだから、順方向と逆方向のそれぞれに対して、関数呼び出しのコードを生成する（Ｓ１１０５）。
【００６５】
また、副作用がある関数が呼び出された場合、グローバル変数やポインタで指されるメモリ上の変数などのエリアシング可能な左辺値は、関数によって書き換えられている可能性がある。データの値と再生式が一致しない状態では再生式は使用できないため、書き換えが行われる可能性があるすべての左辺式、すなわちエリアシング可能な左辺式に対して、再生情報から再生式をクリアしておく必要がある（Ｓ１１０６）。
【００６６】
また、同様に、関数の中で生成されるログの個数は未知であるため、＿ＰＥＥＫ式によってログの古い部分に積まれているデータにアクセスすることができなくなる。従って、参照式に＿ＰＥＥＫ式が含まれる再生情報に対しては参照式をクリアしておく（Ｓ１１０６）。また、この時、古いログにアクセスする位置を求めるために使用していたログ生成個数カウンタもゼロにしておく。
【００６７】
次に、図１２に関数定義のコード生成手順を示す。関数定義では順方向用の関数と逆方向用の関数が一つのプログラムの中に生成されるため、それぞれの関数の名前を付け替えることによって区別できるようにしておく。この時、順方向用関数に対しては関数名の先頭に＿Ｆ＿を付ける。同様に、逆方向用の関数には＿Ｂ＿を付ける（Ｓ１２０２）。
【００６８】
次に、関数本体のコード生成のための準備に入る。まず、再生情報テーブルを初期化して空の状態にする（Ｓ１２０３）。これは、この発明における再生情報が、個々の関数毎に管理されるためで、関数の範囲を超えて左辺値の状態を管理するようにはなっていないからである。そのため、関数毎に個別にテーブルの作成（Ｓ１２０３）と破棄（Ｓ１２１３）を行う。
【００６９】
次に、ローカル変数のための再生情報を割り当てる（Ｓ１２０４）。この時、左辺式、エリアシング可能かどうかの真偽値、参照式、参照依存先については、図４の再生情報割り当て（Ｓ０４１０）と同様に設定する。しかし、再生式については＿ＩＮＶＡＬＩＤＡＴＥ処理を設定しておく。これは、ローカル変数が最初に代入される前は未定義状態であることを示すためのものである。
【００７０】
次に、無条件分岐処理で使用する到達経路番号や、ログ生成個数カウンタなどの関数本体のコード生成時に使用するデータを初期化しておく（Ｓ１２０５）。
【００７１】
次に、関数が割り込みハンドラ用として指定されているかどうかを判定する（Ｓ１２０６）。これは、割り込みハンドラに対しては通常の関数とは異なったフレーム初期化手順やフレーム開放手順を行う必要があるためである。もし、通常の関数である場合は通常関数用のフレーム生成処理を生成する。もし、割り込みハンドラ用と指定されている場合は、割り込みハンドラ用のフレーム生成処理を生成する（Ｓ１２０８）。さらに、割り込みが起こったことを記録するための処理（＿ＩＮＴＥＲＲＵＰＴ＿ＳＴＡＲＴ処理）を順方向プログラム側に生成する（Ｓ１２０９）。
【００７２】
以上の手順によって、関数本体のコード生成の準備が整ったので、プログラム列のコード生成手順を呼び出して関数定義の本体をコード生成する（Ｓ１２１０）。関数本体部分のコード生成が終了したら、そのコード生成手順の中で追加されたローカル変数の分だけフレーム・サイズの情報を修正しておく（Ｓ１２１１）。
【００７３】
次に、関数の終了時に必要になる処理の生成に移る。 ローカル変数と引数については、関数の終了と共に変数の破棄が行われるため、破棄される変数値が再生可能ではないものに対しては順方向プログラム側への保存処理（＿ＳＡＶＥ処理）と、逆方向プログラム側への復帰処理（＿ＲＥＳＴＯＲＥ処理）の生成を行う。また、再生可能あものに対しては再生コードを逆方向プログラム側に生成する（Ｓ１２１２）。
【００７４】
次に、関数本体の中で、ログを生成するような処理が一つも無かった場合は、ダミーのログを生成する処理と、読み込む処理を生成する（Ｓ１２１３）。これは、割り込み発生時点を正確に記録に残すための手段としてログの先頭位置を使用するため、全くログが生成されないような関数があると問題が発生するためである。以上で関数本体のコード生成に関する処理は完了である。関数本体のデータに関する再生情報テーブルは不要になるので削除しておく（Ｓ１２１４）。
【００７５】
最後に、関数終了時のフレーム削除処理を生成する。フレーム削除処理は割り込みハンドラと通常の関数では異なるため、関数がどちらの種類であるかを判定し（Ｓ１２１５）、通常関数である場合は通常のフレーム削除処理を生成する（Ｓ１２１６）。また、割り込みハンドラである場合は、割り込みハンドラが終了したことを記録するログ処理（＿ＩＮＴＥＲＲＵＰＴ＿ＥＮＤ処理）を順方向プログラム側に生成し（Ｓ１２１７）、最後に、割り込みハンドラ用フレーム削除処理を生成する（Ｓ１２１８）。
【００７６】
次に、条件分岐のコード生成手順について図１３に示す。条件分岐では、順方向プログラムの実行時に条件分岐の選択肢のどれが選ばれたのかを何らかの手段で記録しておき、逆方向プログラムはそれを再現することで、プログラムの制御の流れ（制御フロー）を逆向きに辿っていく必要がある。これを実現するためには、条件分岐の選択肢を選ぶための条件式の値が残っていれば良い。
【００７７】
もし条件式の値が再生可能である場合は、再生式を使って条件式の値を再生すればよい。もし再生不可能である場合は、条件式の結果を保持するローカル変数を条件式毎に用意しておき、ローカル変数に条件式の結果を残しておく。このようにする理由は、ログを使って条件式の結果を残した場合、条件分岐のそれぞれの選択肢を実行した結果のログの量がそれぞれ異なるために、条件式のログが積まれている位置が計算できない可能性があるためである。
【００７８】
そのため、まず、条件式を計算した結果をローカル変数に保存する処理を生成し（Ｓ１３０２）、順方向プログラム側では計算結果をすぐに分岐に使用するコードを生成し、逆方向プログラム側にはローカル変数に残っている条件式の結果を使用して分岐するコードを生成する（Ｓ１３０３）。以上によって条件分岐の選択結果を再現すること関する手順は完了である。
【００７９】
次に、それぞれの選択肢の実行コードの生成と、選択肢の実行が終わった後に使用できる再生情報の選択に関する手順を行う。まず選択肢のコード生成の前に、それらのために再生情報テーブルのコピーを作成しておく（Ｓ１３０４）。このコピーした情報を使用してそれぞれの選択肢をコード生成し（Ｓ１３０５，Ｓ１３０６，Ｓ１３０７）、最後に、それぞれの選択肢のコード生成で変更された再生情報テーブルの情報を混合して単一化（マージ）する（Ｓ１３０６）。マージの手順については後述する図１６に示す。これによって、条件分岐を越えた位置で生成されたログや、再生式に関する情報を利用できるようになる。
【００８０】
次に、無条件分岐と、ラベルのコード生成の手順を図１４と図１５に示す。無条件分岐と、ラベルに関する処理はペアになって行われる。まず、無条件分岐側で、順方向プログラム側に経路情報をログに記録する処理が生成される（Ｓ１４０２）。これは、一つのラベルに到達する実行経路が複数ある場合に、どの経路を通ったのかを記録する必要があるためである。次に、ログ生成個数カウンタをインクリメントする（Ｓ１４０３）。これは、＿ＰＥＥＫ式を使ってログにアクセスする際に、ログの位置を計算するのに使用される。
【００８１】
次に、経路番号をインクリメントする（Ｓ１４０４）。これは、それぞれの無条件分岐に対して一意な番号を生成するためである。この経路番号は、逆方向プログラムがラベルから無条件分岐の位置へ逆向きに分岐する際に、飛び先を判別するために使用する（Ｓ１５０２，Ｓ１５０３）。最後に、ラベルのコード生成後に再生情報テーブルを全て削除する処理を行う。失われたデータの再生ができなくなるため、ログの使用効率が下がることになるが、これは、複数の経路からどのような再生情報がもたらされるのかを計算するのが困難であるからである。
【００８２】
次に、再生情報テーブルのマージの手順を図１６に示す。まず、マージ対象の２つのテーブルＡおよびＢと、条件分岐で用いられた条件式を引数として受け取る（Ｓ１６０１）。次にテーブルＡの全ての要素に対して処理が終わるまでループして処理を繰り返す（Ｓ１６０２，Ｓ１６０３，Ｓ１６０９）。もしテーブルＡの要素とまったく同じ要素がテーブルＢにも存在する場合は（Ｓ１６０６）、条件分岐の影響を受けなかったか、または、どちらの経路でも同じ結果になったものであるため、そのままテーブルＡの中に残しておく。
【００８３】
次に、参照式および参照依存先のみが異なる要素があった場合は、２つの参照方法を条件式によって切り替えるような条件式を作成し、参照牛木をそれで置き換えた要素をテーブルＡに残しておくようにする（Ｓ１６０８）。これら以外の要素に対しては、条件分岐の結果による影響が大きすぎるため破棄する（Ｓ１６０７）。最後にマージ結果としてテーブルＡを返して終了する（Ｓ１６０４）。
【００８４】
次に、繰り返し処理（ループ）のコード生成手順について図１７から図１９に示す。繰り返し処理においては、ループの最初の実行の時と２回目以降の処理では異なった経路通ってループ内の処理に到達するため、再生情報が異なってしまうという問題が生じる。２回目のループの時点で異なる情報を持つのは、ループ内で代入が行われる左辺式に関する情報である。そのため、ループ内で更新される左辺式に対してはループの次の周期まで再生情報を引き継がないようにすることで、ループの影響を受けないようにすることができる。ループ内で書き換えられる左辺式の一覧については構文解析段階（図２の０２０５）にて取得できるので、それを利用する。
【００８５】
また同様に、ループではログに積まれるデータの量をあらかじめ計算することができないため、ログを参照するときの位置も計算できなくなるという問題が生じる。これもループの周期を越えてログを参照することが無いようにすることで問題を解決することができる。
【００８６】
図１７に、これらの調整を行う処理の手順を示す。まず、ループが始まる前の位置で、ループ内で更新される全ての左辺式に対して再生式を空に書き換える（Ｓ１７０２，Ｓ１７０３，Ｓ１７０４，Ｓ１７０５）。これによって、ループが開始される前の再生式の情報と、ループの前の周期で書き換えられたと思われる左辺式に関する情報を使用しなくなるので、再生情報が食い違うという問題点を回避することができる。次に、再生情報テーブルの全ての要素に対して、参照式に＿ＰＥＥＫ式が含まれているものを空に書き換える（Ｓ１７０６，Ｓ１７０７，Ｓ１７０８）。これによって、ログの位置を使用して参照する部分が無くなるので、ログの位置計算ができなくなるという問題を回避することができる。最後に、ログの位置に関する情報が失われたのでログの生成個数カウンタもゼロに戻しておく（Ｓ１７０９）。
【００８７】
これらの問題は、ループを実行した後のプログラムに対しても同様に発生するため、ループが終わった直後の位置で同様な再生情報の書き換え処理を行う。
【００８８】
次に、ループの実行回数をどうやって再現するかという問題に対して説明する。これには２つの解決方法がある。一つは、ループした回数を数えて記録する方法で、もう一つは、ループを継続したのか、終了したのかを示すフラグを、ループを実行するたびに残す方法である。ループ回数を数える方式は、ログの使用量が少なくなるという利点があるが、無限にループするような処理に対しては、カウンタがオーバー・フローするという問題があるため使用できない。そのため、ループ回数がカウンタで数えられることが明らかな処理に対してはカウンタによる方法を適用し、無限ループまたはループ回数がカウンタの範囲に収まる保証がないようなループに対しては、実行するたびにフラグを残す方法を適用する。また、ループ回数が固定であるような処理に対しては、ループ・インデックスを逆の順序で生成するようなループ制御処理を生成することによって、ログを全く使用せずに逆向きの処理をすることが可能であるため、それらについては可逆パターン毎に用意した順方向プログラムと逆方法プログラム用のループ制御処理を生成することで対応する。
【００８９】
図１８に、ループ・カウンタを使用する場合のコード生成手順を示す。まず、ループの中で書き換える全ての左辺値に関して、再生情報が問題を起こさないようにするための調整手続き（図１７の手続き）を呼び出す（Ｓ１８０２）。次に、ループが可逆パターンに一致するかを判定する（Ｓ１８０３）。可逆パターンに一致する場合はパターンに基づくコードを順方向プログラムと逆方向プログラムのそれぞれに対して生成する（Ｓ１８０５）。可逆パターンに一致しないようなループの場合は、ループ・カウンタ用のローカル変数を追加し（Ｓ１８０６）、順方向プログラム側にはループの回数を数えるようなコードを生成し（Ｓ１８０７）、ループ終了後にそのカウンタを保存する処理を生成する（Ｓ１８０９）。逆に、逆方向プログラム側では、ログに保存されたカウンタを取り出す処理と、その値の数だけループを繰り返すループ制御コードを生成する（Ｓ１８０７）。最後に、ループによって書き換えられた左辺式に関する再生情報を調整するために調整手続き（図１７の手続き）を呼び出して、再生情報テーブルを整理して終了する（Ｓ１８１０）。
【００９０】
次に、図１９にループを継続したかどうかのフラグをログに残す方法を適用した場合のコード生成手順を示す。この手順は、ループ・カウンタを使用するコード生成手順とほぼ同じであるため、異なった点のみを示す。まず、順方向プログラムのループの前に、逆方向プログラムのループを停止するためのフラグ（ゼロ）をログに残す処理が生成される（Ｓ１９０６）。また、ループの中で行われる処理を生成（Ｓ１９０７）したあと、その最後にループが実行されたことを表すフラグ（１）をログに残す処理が生成される（Ｓ１９０８）。これによって、順方向プログラムの実行時には、まず最初にループを停止するフラグが生成され、つぎにループを実行した数だけ、ループ実行を示すフラグが生成されることになる。逆方向プログラムではこれを読み取って、ループするかどうかを判定するループ制御処理を生成する（Ｓ１９０６）。
【００９１】
次に、関数定義の本体、条件分岐の実行部分、くり返し処理の実行部分に現れるプログラム列をコード生成する手順を図２０に示す。プログラム列は、代入文や関数呼び出しや条件分岐などのプログラムを構成する単位が単純に並んだものである。順方向プログラムのコード生成では、これらのプログラムを１単位分コード生成すること（Ｓ２００８）を続けて、プログラム列の最後に達するまで繰り返せば良い（Ｓ２００２，Ｓ２００３，Ｓ２００４）。
【００９２】
逆方向プログラムは、順方向プログラムと、逆の順序で実行していかなければならない。例えば順方向プログラムで＿Ｆ＿ｆｕｎｃ１（）、＿Ｆ＿ｆｕｎｃ２（）、＿Ｆ＿ｆｕｎｃ３（）の順で関数呼び出しが行なわれる場合は、逆プログラム側では＿Ｂ＿ｆｕｎｃ３（）、＿Ｂ＿ｆｕｎｃ２（）、＿Ｂ＿ｆｕｎｃ１（）の順序で関数を呼び出さなければならない。そのため逆方向プログラム側ではプログラムを１単位分コード生成するたびに、逆の順序になるようにコードを並べる（Ｓ２００４）。
【００９３】
またこの時、順方向プログラムと、逆方向プログラムの対応関係を表す情報も生成する（Ｓ２００５）。これは障害解析手段（デバッガ）が順方向プログラムの停止した個所が、逆方向プログラムの何処にあたるのかを求めるのに使用する。生成される対応関係テーブルのデータ構造を図２８に示す。このテーブル（２８０１）では、ユーザーの便利性を高めるためプログラム上の位置をソースコードの行で管理する。そのため、順方向プログラムと逆方向プログラムに対して、それぞれがソースコードのどの行に相当するのかの情報（２８０２）と、どのアドレスに配置されたのかを示す情報（２８０３，２８０４）が生成される。
【００９４】
次に、プログラム全体のコード生成手順を図２１に示す。プログラム全体は手続き（関数定義）の並びで構成されるため、プログラム列の場合と異なり、生成されるコードの並び順と実行順序は無関係である。そのため、順方向プログラム側でも逆方向プログラム側でも同じように、全ての関数定義を順番にコード生成していくだけで良い（Ｓ２１０２，Ｓ２１０３）。
【００９５】
次に、これまでのコード生成手順で順方向と逆方向のそれぞれのプログラムに埋め込まれてきたログ処理の内容について説明する。図２２に＿ＳＡＶＥ処理、図２３に＿ＲＥＳＴＯＲＥ処理、図２４に＿ＰＥＥＫ処理の処理内容を示す。これらの処理手続きはログ領域へのデータの保存と取り出しを行なうために使用する。
【００９６】
図２２に示す＿ＳＡＶＥ処理では、ログに保存すべきデータが、メモリ上のどこにあるのかを示すアドレスと、そのデータのサイズを受け取り（Ｓ２２０１）、指定された分だけデータをログ領域にコピー（Ｓ２２０２）したあと、ログの先頭を指すポインタを更新する（Ｓ２２０３）。もしこの時、ログ領域をすべて使い切ってしまった場合は、何らかの処置が必要であるため、デバッガに対してそれを通知する（Ｓ２２０４，Ｓ２２０５）。
【００９７】
図２３に示す＿ＲＥＳＴＯＲＥ処理は、＿ＳＡＶＥ処理と全く逆の手順でログ領域からデータを取り出す。まず、取り出したデータをどこに格納すべきかを示すアドレスと、データのサイズを受け取り（Ｓ２３０１）、ログ領域にデータが全く無い場合はデバッガに対してそれを通知する（Ｓ２３０２，Ｓ２３０３）。次にデータ・サイズの分だけログの先頭を指すポインタを戻し（Ｓ２３０４）、指定されたデータ・サイズの分だけ、データをコピー先にコピーする（Ｓ２３０５）。
【００９８】
図２４に示す＿ＰＥＥＫ処理は、ログ領域そのものは更新せず、ログの先頭から指定されたサイズだけずれた位置からデータをコピーする。まずコピー先アドレスと、データのサイズ、および、ログの先頭からのオフセットのサイズを受け取る（Ｓ２４０１）。つぎに、指定されたオフセットの位置から、指定されたデータ・サイズの分だけコピー先にデータをコピーする（Ｓ２４０３）。
【００９９】
次に＿ＩＮＶＡＬＩＤＡＴＥ処理について図２５に示す。＿ＩＮＶＡＬＩＤＡＴＥ処理は、逆プログラムの実行によって、ローカル変数の状態が最初の代入が行なわれる前の状態に戻ったことをデバッガに通知するために使用される。そのため、＿ＩＮＶＡＬＩＤＡＴＥ処理は、デバッガへの通知処理のみで構成される（Ｓ２５０２）。このような処理が必要になるのは、ローカル変数では最初の代入が行なわれる前のメモリの状態が不定であるためである。デバッガは＿ＩＮＶＡＬＩＤＡＴＥであると指定されたメモリ領域の内容を表示するように指示された場合は、それが不定であることを表示する。
【０１００】
次に、割り込みハンドラの先頭と最後に挿入される＿ＩＮＴＥＲＲＵＰＴ＿ＳＴＡＲＴ処理と、＿ＩＮＴＥＲＲＵＰＴ＿ＥＮＤ処理を、図２６と図２７に示す。これらの処理は割り込みが、いつ、どこで発生したのかを記録すために使用される。データを記録する領域は通常のログとは異なり、割り込みログのみを記録するための専用の領域に保存される。これは割り込みがいつ発生するかが不定であるため、通常のログ情報と、割り込みを示すログ情報を区別することが困難であるためである。
【０１０１】
割り込みログ領域へのデータの書き込みと取り出しの手順は、割り込みログ領域を対象とする点以外は、＿ＳＡＶＥ処理と＿ＲＥＳＴＯＲＥ処理と同じ手順を使用する。
【０１０２】
図２６に示す＿ＩＮＴＥＲＲＵＰＴ＿ＳＴＡＲＴ処理は、順方向プログラム側の割り込みハンドラの先頭で呼び出される処理で、割り込みが発生したアドレスをログに保存する（Ｓ２６０２）。また、図２７に示す＿ＩＮＴＥＲＲＵＰＴ＿ＥＮＤ処理は、順方向プログラム側の割り込みハンドラの最後で呼び出される処理で、割り込みハンドラがいつ終了したのかを記録する（Ｓ２７０２）。これにはログ領域の先頭を指すポインタの情報を使用する。このポインタは関数の呼び出しや、ループなど、一つのアドレスを何度も実行するうな場合に、どの実行時に割り込みが起きたのかを特定するのに使用する。逆方向プログラムの実行では、この情報を基にデバッガが割り込みの発生を模擬することで割り込み処理を逆方向に辿って溯ることが可能となる。
【０１０３】
次に、障害解析手段（デバッガ）の処理手順について説明する。障害解析手段は解析対象のデータの表示、書き換え、プログラムのロード、ブレークポイントの設定と実行など、多様な機能を持つのが普通であるため、この発明の中心的課題である逆方向実行に関連した部分のみ説明する。
【０１０４】
図２９に逆方向実行時の処理手順を示す。まず最初に、逆方向プログラムのどこから実行を始めるのかを決定するため、順方向プログラムが停止したアドレスを取得し（Ｓ２９０２）、次にそのアドレスを対応関係テーブル（図２８）を用いて逆方向プログラム側のアドレスに変換する（Ｓ２９０３）。
【０１０５】
次に、ユーザーに対して、ソースコードのどの位置まで逆方向実行をするのかを指示してもらう（Ｓ２９０６）。次に、ユーザーが指示したソースコード上の位置を、対応関係テーブルを用いて逆方向プログラム側のアドレスに変換し（Ｓ２９０８）、そのアドレスに対してブレーク・ポイントを設定する（Ｓ２９０９）。次に、逆方向プログラムの実行を行なって（Ｓ２９１０）、そのブレーク・ポイントの位置まで到達したら逆実行を終了して（Ｓ２９１１）、ユーザーからの次の指示を待つ（Ｓ２９０６）。もしユーザーが終了を指示した場合は逆方向実行を終了する（Ｓ２９０７，Ｓ２９１２）。
【０１０６】
ただし、このときデバッガは割り込みの発生も模擬する必要がある。そのため逆方向プログラムの実行を開始する前に割り込みログの内容を読み込み（Ｓ２９０４）、全ての割り込み発生アドレスに対してブレーク・ポイントを設定する（Ｓ２９０５）。これによって割り込み発生アドレスを通過するたびに逆方向実行が中断するため、割り込みが発生した時点まで溯ったかどうかをログの先頭を指すポインタの値を比較して判定し（Ｓ２９１３）、割り込み発生時点に到達したら、逆方向プログラム側の割り込みハンドラを呼び出す処理を行なう（Ｓ２９１４）。
【０１０７】
上述したように、本実施の形態では、プログラムの障害解析において、プログラムを逆順に実行して行くことによってプログラムの過去の状態を再現することができるため、プログラムが障害に至るまでの全ての過程を調べることが出来、プログラムの障害解析が容易になるという効果が得られる。
【０１０８】
また、ログ情報として、逆命令、アドレス、サイズなどの情報がログに記録される従来の逆命令ログ法に対して、本実施の形態では、逆方向プログラムを実行することでこれらの情報が得られるため、ログに記録する必要が無く、ログに必要なメモリ量が削減されるため、同一メモリ量で逆方向実行が可能な範囲が拡大されるという効果が得られる。
【０１０９】
さらに、逆方向プログラムを最適化することが可能であるため、逆命令ログ法と比較して高速に実行できるという効果が得られる。
【０１１０】
【発明の効果】
以上のように、この発明によれば、命令の種類の情報と、命令が操作するメモリのアドレス、およびデータ・サイズの情報を、逆方向プログラムの形でログから分離することで、ログの記録に必要なメモリの量を削減し、同一メモリ量で逆方向実行が可能な範囲を拡大することができるソフトウエア障害解析方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】  この発明の実施の形態に係る障害解析時のハードウェア構成とメモリ内部のソフトウェア構成を示す図である。
【図２】  コンパイルの処理フロー図である。
【図３】  再生情報テーブルのデータ構造を示す図である。
【図４】  代入処理のコード生成手順を示すフローチャートである。
【図５】  再生可能性の判定手順を示すフローチャートである。
【図６】  参照可能性の判定手順を示すフローチャートである。
【図７】  再生コードの生成手順を示すフローチャートである。
【図８】  参照コードの生成手順を示すフローチャートである。
【図９】  自己破壊代入の回避処理生成手順を示すフローチャートである。
【図１０】  式のコード生成手順を示すフローチャートである。
【図１１】  関数呼び出しのコード生成手順を示すフローチャートである。
【図１２】  関数定義のコード生成手順を示すフローチャートである。
【図１３】  条件分岐のコード生成手順を示すフローチャートである。
【図１４】  無条件分岐のコード生成手順を示すフローチャートである。
【図１５】  ラベルのコード生成手順を示すフローチャートである。
【図１６】  再生情報テーブルのマージ手順を示すフローチャートである。
【図１７】  繰り返し処理用の再生情報テーブル調整手順を示すフローチャートである。
【図１８】  繰り返し処理のコード生成手順（ループ・カウンタを使用する場合）を示すフローチャートである。
【図１９】  繰り返し処理のコード生成手順（ループ・ログを使用する場合）を示すフローチャートである。
【図２０】  プログラム列のコード生成手順を示すフローチャートである。
【図２１】  プログラム全体のコード生成手順を示すフローチャートである。
【図２２】  ＿ＳＡＶＥ処理の処理内容を示すフローチャートである。
【図２３】  ＿ＲＥＳＴＯＲＥ処理の処理内容を示すフローチャートである。
【図２４】  ＿ＰＥＥＫ処理の処理内容を示すフローチャートである。
【図２５】  ＿ＩＮＶＡＬＩＤＡＴＥ処理の処理内容を示すフローチャートである。
【図２６】  ＿ＩＮＴＥＲＲＵＰＴ＿ＳＴＡＲＴ処理の処理手順を示すフローチャートである。
【図２７】  ＿ＩＮＴＥＲＲＵＰＴ＿ＥＮＤ処理の処理手順を示すフローチャートである。
【図２８】  対応関係テーブルのデータ構造を示す図である。
【図２９】  障害解析手段（デバッガ）の処理手順を示すフローチャートである。
【符号の説明】
０１０１  計算機全体、０１０２  中央処理装置（プロセッサ）、０１０３  メモリ、０１０４  順方向プログラム、０１０５  逆方向プログラム、０１０６障害解析手段（デバッガ）、０１０７  データ領域、０１０８  ログ領域、０１０９  割り込みログ領域、０１１０  制御端末、０２０１  ソース・プログラム、０２０２  コンパイラ全体、０２０３  ソース読み込み処理、０２０４  字句解析処理、０２０５  構文解析処理、０２０６  構文木最適化処理、０２０７順方向プログラムのコード生成処理、０２０８  逆方向プログラムのコード生成処理、０２０９  コード最適化処理、０２１０  コード出力処理、０２１１  対応関係テーブル出力処理、０２１２  コンパイル結果のファイル（実行プログラム）、０２１３  順方向プログラム、０２１４  逆方向プログラム、０２１５対応関係テーブル、２８０１  対応関係テーブル、２８０２  ソース・プログラムの行の情報、２８０３  順方向プログラムのアドレス、２８０４  逆方向プログラムのアドレス。
【図１】
0004107470.tif 000002
【図２】
0004107470.tif 000003
【図３】
0004107470.tif 000004
【図４】
0004107470.tif 000005
【図５】
0004107470.tif 000006
【図６】
0004107470.tif 000007
【図７】
0004107470.tif 000008
【図８】
0004107470.tif 000009
【図９】
0004107470.tif 000010
【図１０】
0004107470.tif 000011
【図１１】
0004107470.tif 000012
【図１２】
0004107470.tif 000013
【図１３】
0004107470.tif 000014
【図１４】
0004107470.tif 000015
【図１５】
0004107470.tif 000016
【図１６】
0004107470.tif 000017
【図１７】
0004107470.tif 000018
【図１８】
0004107470.tif 000019
【図１９】
0004107470.tif 000020
【図２０】
0004107470.tif 000021
【図２１】
0004107470.tif 000022
【図２２】
0004107470.tif 000023
【図２３】
0004107470.tif 000024
【図２４】
0004107470.tif 000025
【図２５】
0004107470.tif 000026
【図２６】
0004107470.tif 000027
【図２７】
0004107470.tif 000028
【図２８】
0004107470.tif 000029
【図２９】
0004107470.tif 000030