2009年09月14日

DWARF と有限状態機械

DWARF はソースレベルデバッギングのための情報をオブジェクトファイル中に保持する際のデータフォーマットです。

ソースレベルデバッガが最低限必要とする情報として、ソースコード中のプログラム行の位置と、対応するマシン命令アドレスの表があります。特にコンパイラによる高度な最適化が入ってくると、1つの行から不連続なアドレスにマシン命令が生成されるようになってくるので、デバッグ情報が無ければ、どこのアドレスにブレークポイントを張れば良いのか、ステップ実行の時にどこで止めれば良いのか、などが全くわからなくなってしまいます。

この対応表は非常に巨大なものに成り得るので、DWARFは対応表をそのまま持つのではなく、行番号プログラム(line number program)によって対応表を生成するという仕様になっています。これは、JVMの仮想機械語のようなバイトコードプログラムとなっています。具体的には、ソースコードのファイル名、行/列番号、命令アドレスなどを状態とする有限状態機械を定義し、その仮想機械のバイトコード列(= 行番号プログラム)をデバッグ情報として保持します。



DWARF 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;
}

だいぶ長くなってしまいました。次回は行番号プログラムヘッダと各バイトコード命令について見ていきます。

トラックバックURL

コメントする

名前
 
  絵文字
 
 
記事検索
最新コメント
「最新トラックバック」は提供を終了しました。
アクセスカウンター
  • 今日:
  • 昨日:
  • 累計:

QRコード
QRコード