アルゴリズムとデータ構造1

コンパイラ
2012年11月8日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
例外処理
プログラムの実行中に発生した、例外的な事象を取り扱
うこと。


例外的な事象に対処するために、大域的なジャンプにより、
例外処理プログラムに処理を移す。
例外的な事象として、例えば次のようなもの。




スタックのオーバーフロー
セグメンテーション違反・nullポインタ例外
０除算
例外処理の実装について。




2
プログラミング言語
ＯＳ
プロセッサ
原始的な実装
ＯＳが存在していれば、ＯＳの例外処理機構を利用する。



各プロセスにシグナルとして実装されている。
例外の発生により、対応するシグナルハンドラが呼ばれる。


例外発生によりＯＳに処理が戻るとともにプロセスは停止し、
シグナルハンドラからプロセスの実行を再開する。
ＯＳの機能なので、システムコールで使える。

プロセッサが検出でき、ＯＳが受けた例外の一部しか対応できない。
プロセッサの例外処理機構を利用する。


例外の発生により、発生源に固有のアドレスへジャンプする。


高級言語からの言語仕様の範囲内での利用は不可能。

3
たいていは、最低限のレジスタはスタックに退避してあるので、
原因を除去できれば復帰できる。
言語拡張かアセンブリ記述を使うしかない。
例外処理の例（110ページ）
1. class Example {
2.
public static void main(String[] args){
3.
try{
4.
method1(args);
5.
System.out.println("This Line is not executed.");
6.
}
7.
catch(Exception e){ // Exception （かその派生クラス）に関する例外ハンドラ
8.
System.out.println(e.getMessage());
9.
}
10.
}
11.
static void method1(Object o){
12.
synchronized(o){
13.
method2();
14.
System.out.println("This Line is not executed.");
15.
}
16.
}
17.
staic void method2(){
18.
throw (new Exception("Jump To Handler."));
// 例外発生源
19.
}
20. }
4
例外処理の実行手順
例外発生により、すぐに大域的ジャンプが発生するのではない。
｛20行目で例外が生成され投げられたので、20行目を検査すると try ブロッ
クの中にはない。よって、｝ methdo2() から抜けて呼び出し元に戻る。
｛呼び出し元の14行目を検査すると、14行目が try ブロックの中にはない。
ただし、synchronized ブロックの中にあるので、いきなり呼び出し元にに戻
るわけにはいかない。13行目で synchronized ブロックに突入する際に、指
定した変数 o が参照するインスタンスの排他制御権を確保したので、例外
処理とはいえども、確保した排他制御権を synchronized ブロックから抜ける
ときに開放するべきである。よって、｝呼び出し元の14行目に着いたら排他
制御権を開放し、続いて呼び出し元に戻る。
｛呼び出し元の4行目を検査すると、try ブロックの中にあり、後続のcatch
節は7行目にある。よって、｝呼び出し元の4行目に着いたら catch 節のある
7行目にジャンプし、投げられた例外が7行目の catch 節において捕捉すべ
きインスタンスか検査する。結果として捕捉すべき例外でることから、8行目
にある例外処理を行う。

1.
2.
3.
5
例外処理のコンパイル法
コンパイル時に実行できる部分



中括弧で囲んだ部分。
try ブロックや synchronized ブロックの中にあるかどうか
は、構文解析すればわかる。

コンパイル時にできる検査はあらかじめ済ませておき、実行時に
しか実行できないコードを出力する。
実行時にしか実行できない部分。



中括弧の外側。
戻る・捕捉するといった分岐・条件分岐。


インスタンスの実行時の型の検査。

6
プログラマが思うところで、例外処理できる。
プログラマが例外を自由に設計できる。
例外処理のコード生成
ソースコード中の例外の発生源となりうる場所について、
取るべき動作を決める。


発生源としては throw の他にメソッド呼び出しも考慮する。


呼び出した先から捕捉されなかった例外が伝播してくる。
例外発生場所に基づき、取るべき動作を決定する。



try ブロックの中では、対応する catch の検査・分岐。
synchronized ブロックの中では、排他制御権の開放。
メソッドから呼び出し元に例外処理として戻る。
決めた動作に基づいてコードを生成する。


メソッドから戻ったとき、通常処理か例外処理の区別。

7
通常通り戻るか、例外を捕捉・伝播する。
２返戻値法による実装
メソッドの返戻値を２つとする方法。



メソッドの定義で明示した戻り値。
例外発生フラグ。

メソッド呼び出し直後に、フラグを調べ、対応する例外処理を行う。


例外の伝播：メソッドから抜けて呼び出し元に戻る。
例外の捕捉：対応する catch 節にジャンプする。
通常処理と例外処理のフローが一時重なることが問題


呼び出し直後でフラグでフローを分離する処理コスト。


8
通常処理フローの中から例外処理を分離する非合理さ。
そもそも、例外処理を通常処理フローに合流しなければ発生しない。
説明用プログラムの共通定義
例外を処理する関数へのポインタを定義。
発生した例外に対応する処理関数への参照を
そのポインタに代入することで実装する。


２値返戻法では、メソッド（関数）の実行ごとに検査。
表引き法では、戻り番地から例外処理を引き出す。


1.
2.
3.
4.
5.
6.
7.
8.
struct ExecEnv { // スレッド固有の資源を収める構造体
…
void *exception;
// 例外発生フラグ。発生した例外への参照
…
};
#define exceptionOccurred(ee) ((ee)->exception != NULL)
#define excpetionThrow(ee, obj) ((ee)->exception = obj)
#define exceptionClear(ee) ((ee)->exception = NULL)
9
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
void Example8_main(ExecEnv *ee, void *args){
Example8_method1(ee, args);
if(exceptionOccured(ee)){
goto CATCH;
}
println(ee, System.out, "This Line is not executed.");
if(exceptionOccured(ee)){
goto CATCH;
}
NORMAL_EXIT:
return;
CATCH:
{
void *object = ee->exception;
if(is_instance_of(object, Exception, ee)){
exceptionClear(ee);
println(ee, System.out, getMessage(ee, object));
if(exceptionOccured(ee)){
goto EXCEPION_EXIT;
}
goto NORMAL_EXIT;
}
}
EXCEPTION_EXIT:
return;
}
10
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
void Example8_method1(ExecEnv *ee, void *o){
EnterSynchronizedBlock(o);
if(exceptionOccured(ee)){
goto EXCEPTION_EXIT;
}
Example_method2(ee);
if(exceptionOccured(ee)){
goto SYNCHRONIZED_BLOCK_EXCEPTION_EXIT;
}
println(ee, System.out, "This Line is not executed.");
if(exceptionOccured(ee)){
goto SYNCHRONIZED_BLOCK_EXCEPTION_EXIT;
}
ExitSynchronizedBlock(o);
if(exceptionOccured(ee)){
61. void Example8_method2(ExecEnv *ee){
goto EXCEPTION_EXIT;
62.
void *object = newInstance(ee, Exception);
}
63.
if(exceptionOccured(ee)){
return;
64.
goto EXCEPTION_EXIT;
SYNCHRONIZED_BLOCK_EXCEPTION_EXIT;
65.
}
ExitSynchronizedBlock(o);
66.
Exception_init(ee, object, "Jump to Handler.");
EXCEPTION_EXIT:
67.
if(exceptionOccured(ee)){
return;
68.
goto EXCEPTION_EXIT;
}
69.
}
70.
exceptionThrow(ee, object);
71. EXCEPTION_EXIT:
72.
return;
73. }
11
表引き法による実装

メソッドからの戻りを例外の場合はreturnで処理しない。


フラグで分離した先へ goto でもってメソッドから戻る。
例外発生のときの戻り番地をあらかじめ知る方法を用意。

12
通常の戻り先をキーに、例外処理の分岐先を取り出す。
戻り番地
例外発生時の戻り番地
3
6
4
6
12
15
21
27
22
25
23
25
24
25
24
27
27
27
33
36
34
36
プログラム中のどこから来たか？
という情報よりも
どこへ戻るのか？
という情報を使う。
呼ばれた関数の
スタックフレーム
戻り番地
それは、戻り番地は暗黙的に渡されているため、
特別に処理しなくても獲得できる情報だから。
ee
args
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
void Example8_main(ExecEnv *ee, void *args){
Example8_method1(ee, args);
println(ee, System.out, "This Line is not executed.");
NORMAL_EXIT:
return;
CATCH:
{
void *object = ee->exception;
if(is_instance_of(object, Exception, ee)){
exceptionClear(ee);
println(ee, System.out, getMessage(ee, object));
goto NORMAL_EXIT;
}
}
EXCEPTION_EXIT:
goto (lookUpReturnAddressInException(returnAddress());
}
呼んだ関数の
スタックフレーム
13
← TOS
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
void Example8_method1(ExecEnv *ee, void *o){
EnterSynchronizedBlock(o);
Example_method2(ee);
println(ee, System.out, "This Line is not executed.");
ExitSynchronizedBlock(o);
return;
SYNCHRONIZED_BLOCK_EXCEPTION_EXIT;
ExitSynchronizedBlock(o);
EXCEPTION_EXIT:
goto (lookUpReturnAddressInException(returnAddress());
}
void Example8_method2(ExecEnv *ee){
void *object = newInstance(ee, Exception);
Exception_init(ee, object, "Jump to Handler.");
exceptionThrow(ee, object);
EXCEPTION_EXIT:
goto (lookUpReturnAddressInException(returnAddress());
}
14
Null Pointer Exception

実行時例外のいくらかはプロセッサが検出できる






セグメンテーション違反（IA-32では、一般保護例外）
ページ不在例外
０除算例外
バスエラー（IA-32では、一般保護例外）
プロセッサが検出できるものについては、検査コードを
生成しないで、シグナルなどを経由してプロセッサから
例外を受け取る。
null pointer は特定のアドレス値に設定してある。


15
その番地を｛コード｜データ｝セグメントに入れないでおく。
ページ管理表で、その番地を含むページを不在状態にしておく。
[Intel, ``Software Developer Manual’’]
ページングとセグメンテーションは組み合わされることが多い

Download Report