2009年09月14日
DWARF と有限状態機械
DWARF はソースレベルデバッギングのための情報をオブジェクトファイル中に保持する際のデータフォーマットです。
ソースレベルデバッガが最低限必要とする情報として、ソースコード中のプログラム行の位置と、対応するマシン命令アドレスの表があります。特にコンパイラによる高度な最適化が入ってくると、1つの行から不連続なアドレスにマシン命令が生成されるようになってくるので、デバッグ情報が無ければ、どこのアドレスにブレークポイントを張れば良いのか、ステップ実行の時にどこで止めれば良いのか、などが全くわからなくなってしまいます。
この対応表は非常に巨大なものに成り得るので、DWARFは対応表をそのまま持つのではなく、行番号プログラム(line number program)によって対応表を生成するという仕様になっています。これは、JVMの仮想機械語のようなバイトコードプログラムとなっています。具体的には、ソースコードのファイル名、行/列番号、命令アドレスなどを状態とする有限状態機械を定義し、その仮想機械のバイトコード列(= 行番号プログラム)をデバッグ情報として保持します。
ソースレベルデバッガが最低限必要とする情報として、ソースコード中のプログラム行の位置と、対応するマシン命令アドレスの表があります。特にコンパイラによる高度な最適化が入ってくると、1つの行から不連続なアドレスにマシン命令が生成されるようになってくるので、デバッグ情報が無ければ、どこのアドレスにブレークポイントを張れば良いのか、ステップ実行の時にどこで止めれば良いのか、などが全くわからなくなってしまいます。
この対応表は非常に巨大なものに成り得るので、DWARFは対応表をそのまま持つのではなく、行番号プログラム(line number program)によって対応表を生成するという仕様になっています。これは、JVMの仮想機械語のようなバイトコードプログラムとなっています。具体的には、ソースコードのファイル名、行/列番号、命令アドレスなどを状態とする有限状態機械を定義し、その仮想機械のバイトコード列(= 行番号プログラム)をデバッグ情報として保持します。
DWARF 3 の規格書
http://dwarfstd.org/Dwarf3.pdf
の 92 ページ (PDF だと 104 ページ) から Line Number Information の仕様が定義されています。
状態機械は以下のようなレジスタ（状態）を持ちます。
各状態はターゲットマシン命令と対応します。
5つの状態(符号無し整数)
5つのフラグ(boolean)
基本ブロック(basic block)とはコンパイラの用語で、内部に分岐を含まない命令列のことです。最後の命令は多くの場合、(手続き呼び出しなどを含む)他の基本ブロックへ制御を移す命令となります。(基本ブロックの先頭のみが、他のコードからのジャンプターゲットと成り得ます。)基本ブロックは、ソースコード上の表現とは独立しています。
ja.wikipedia:基本ブロック
http://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html
状態機械の初期状態は以下の通りです。
状態機械のバイトコード命令には3つの種類があります。
standard opcodeのそれぞれのオペランド数は行番号プログラムヘッダでも指定されているそうです。
LEB128可変長データ表現の詳細については付録 3 を参照してください。符号無しの場合は簡単です。
だいぶ長くなってしまいました。次回は行番号プログラムヘッダと各バイトコード命令について見ていきます。
http://dwarfstd.org/Dwarf3.pdf
の 92 ページ (PDF だと 104 ページ) から Line Number Information の仕様が定義されています。
状態機械は以下のようなレジスタ（状態）を持ちます。
各状態はターゲットマシン命令と対応します。
5つの状態(符号無し整数)
- address
- プログラムカウンタ(命令アドレス)値
- file
- ファイル名に対応するID(行番号プログラムヘッダ内に存在するファイルエントリ配列の添字)
- line
- 1から始まる行番号
- column
- 1から始まる列番号(0にはソースコード行の左端から開始する文という特別な意味がある)
- isa
- 命令セットアーキテクチャをエンコードした値(0がデフォルト) 例 : ARM/Thumb/Thumb2 など。
5つのフラグ(boolean)
- is_stmt
- 現在の命令はブレークポイントを張るのにちょうど良いところか?
- basic_block
- 現在の命令は基本ブロックの先頭か?
- end_sequence
- 現在のアドレスはターゲットマシン命令(バイト列)が終わった直後(最初のバイト)か?
- prologue_end
- 現在のアドレスは(関数に対してブレークポイントが張られていて、関数に突入する時に実行を停止するべき)関数プロローグ時ブレークポイント(複数可)か ?
- epilogue_begin
- 現在のアドレスは(関数に対してブレークポイントが張られていて、関数を抜ける時に実行を停止するべき)関数エピローグ時ブレークポイント(複数可)か?
基本ブロック(basic block)とはコンパイラの用語で、内部に分岐を含まない命令列のことです。最後の命令は多くの場合、(手続き呼び出しなどを含む)他の基本ブロックへ制御を移す命令となります。(基本ブロックの先頭のみが、他のコードからのジャンプターゲットと成り得ます。)基本ブロックは、ソースコード上の表現とは独立しています。
ja.wikipedia:基本ブロック
http://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html
状態機械の初期状態は以下の通りです。
- address
- 0
- file
- 1
- line
- 1
- column
- 0
- isa
- 0
- is_stmt
- 行番号プログラムヘッダ内のdefault_is_stmtにより決定
- basic_block
- false
- end_sequence
- false
- prologue_end
- flase
- epilogue_begin
- false
状態機械のバイトコード命令には3つの種類があります。
- special opcodes
- 1バイト命令
- standard opcodes
- 1バイト命令、可変長オペランド(LEB128エンコード)
- extended opcodes
- 値0のバイトで始まり、LEB128エンコードされた命令の長さが続き、可変長(LEB128)の命令本体(1バイトのextended opcodeから開始)が続きます。
standard opcodeのそれぞれのオペランド数は行番号プログラムヘッダでも指定されているそうです。
LEB128可変長データ表現の詳細については付録 3 を参照してください。符号無しの場合は簡単です。
エンコード(擬似コード)
do {
byte = low order 7 bits of value;
value >>= 7;
if (value != 0) /* more bytes to come */
set high order bit of byte;
emit byte;
} while (value != 0);
デコード
result = 0;
shift = 0;
while (true) {
byte = next byte in input;
result |= (low order 7 bits of byte << shift);
if (high order bit of byte == 0)
break;
shift += 7;
}
だいぶ長くなってしまいました。次回は行番号プログラムヘッダと各バイトコード命令について見ていきます。
