llvm : 例外処理

llvm(2.6)での例外処理。
例外処理のドキュメン*1は一応用意されているのだが、簡潔かつ実例が皆無なので、試すのに結構苦労した。
以下は、その簡単なまとめとメモ。

llvmでの例外処理の種類

llvmであらかじめサポートされている(?)例外処理の方法は三つ。

  1. invoke命令/unwind命令*2を組み合わせる
  2. Itanium ABIに基づいた(or DWARFを用いた)例外処理 ※ 例外捕捉のコストは高いが、例外を送出しなければほぼゼロコスト(速度的に)
  3. setjump/longjumpを用いた例外処理 ※ 例外捕捉のコストは低いが、例外を送出しない場合にもコストが必要(速度的に)

後者二つは、C++(gcc?)で使われている例外処理をそのまま利用する形となっており、自分の環境のllvmがどちらの例外処理を(少なくともあまり労力をかけずに)使えるかは、その環境のgccがどっち用にコンパイルされているかで決まる*3※ setjump/longjumpを用いる例外処理は、僕の環境では上手く使うことができなかった。そのため以降でもこの方法には触れない。

最初のものは、例外処理そのものというよりは、大域脱出/捕捉のための命令なので、その上に例外処理用の仕組みを構築する必要がある。
ちなみに、バージョン2.6のllvmでは、invoke/unwindを用いているコードは、最終的にsetjump及びlongjumpに変換されるようなので、性能的には三番目のsetjump/longjump例外処理に近い。

実例

「ループの中で乱数を生成し、その結果が0となる数をカウントする」という処理を行うプログラムを例外を使って実装してみる。

最初は、invoke命令とunwind命令を組み合わせる方法:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; ファイル名: unwind.ll
;;;; コンパイル: llvm-as unwind.ll -o - | opt -lowerinvoke -enable-correct-eh-support -o unwind.bc
;;;; 実行方法:   lli unwind.bc <生成される乱数の最大値> <ループ回数>
;;;; 
;;;; [注釈]
;;;;  'lowerinvoke'及び'enable-correct-eh-support'オプションを指定したoptコマンドを経由すると、
;;;;  invoke/unwindが、setjump/longjumpを用いたコードに変換され、正常に扱われるようになる。

;;; printfの書式文字列とカウンタ変数
@FMT = internal constant [4 x i8] c"%d\0A\00"
@COUNTER = internal global i32 0

;;; 各種宣言
declare i32 @rand()
declare i32 @atoi(i8*)
declare void @printf(i8*,i32)

;;; コマンド引数を数値に変換する補助関数
define i32 @argv2int(i8** %argv,i32 %index) {
  %arg1 = getelementptr i8** %argv, i32 %index
  %a    = load i8** %arg1
  %i    = call i32 @atoi(i8* %a)
  ret i32 %i
}

;;; 例外送出関数: 乱数を生成して、0なら例外を送出する
define void @throw_fn(i32 %max) {
  %n1 = call i32 @rand()
  %n2 = urem i32 %n1, %max
  %b = icmp eq i32 %n2, 0

  br i1 %b, label %OTHER, label %ZERO
ZERO:
  ret void

OTHER:
  unwind
}

;;; ループ関数
define void  @try_catch_loop(i32 %max, i32 %repeat) {
ENTRY:
  br label %LOOP

LOOP:
  %n  = phi i32 [0,%ENTRY],[%n1,%NEXT],[%n1,%INC_AND_NEXT]

  %b = icmp eq i32 %n, %repeat
  br i1 %b, label %END, label %CALL

CALL:
  %n1 = add i32 %n, 1  
  invoke void @throw_fn(i32 %max) to label %NEXT unwind label %INC_AND_NEXT
NEXT:
  br label %LOOP

INC_AND_NEXT:
  ;; 例外が送出された場合、カウンタを+1して、次のループへ
  %t1 = load i32* @COUNTER
  %t2 = add i32 %t1, 1
  store i32 %t2, i32* @COUNTER
  br label %LOOP

END:
  ret void
}

;;; メイン関数
define i32 @main(i32 %argc, i8** %argv) {
  %max    = call i32 @argv2int(i8** %argv, i32 1)
  %repeat = call i32 @argv2int(i8** %argv, i32 2)

  call void @try_catch_loop(i32 %max, i32 %repeat)
  %throw_cnt = load i32* @COUNTER
  
  call void @printf(i8* getelementptr([4 x i8]* @FMT, i32 0, i32 0) ,i32 %throw_cnt)
  ret i32 0
}

次がDWARFを用いる方法:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; ファイル名: dwarf.ll
;;;; コンパイル: llvm-as dwarf.ll -o - | llc -enable-eh o dwarf.s; g++ -o dwarf dwarf.s
;;;; 実行方法:   dwarf <生成される乱数の最大値> <ループ回数>
;;;; 
;;;; [注釈]
;;;;  DWARF例外処理を用いる場合、ネイティブコードにコンパイルしないと例外補則に失敗する

;;;; unwind.llとの共通部分
@FMT = internal constant [4 x i8] c"%d\0A\00"
@COUNTER = internal global i32 0

declare i32 @rand()
declare i32 @atoi(i8*)
declare void @printf(i8*,i32)

define i32 @argv2int(i8** %argv,i32 %index) {
  %arg1 = getelementptr i8** %argv, i32 %index
  %a    = load i8** %arg1
  %i    = call i32 @atoi(i8* %a)
  ret i32 %i
}

define i32 @main(i32 %argc, i8** %argv) {
  %max    = call i32 @argv2int(i8** %argv, i32 1)
  %repeat = call i32 @argv2int(i8** %argv, i32 2)

  call void @try_catch_loop(i32 %max, i32 %repeat)
  %throw_cnt = load i32* @COUNTER
  
  call void @printf(i8* getelementptr([4 x i8]* @FMT, i32 0, i32 0) ,i32 %throw_cnt)
  ret i32 0
}

;;;; DWARF用コード
;;; C++のint型のtype_info構造体への参照
%type_info = type {{i8*,i8*}}
@_ZTIi = external constant %type_info

;;; 例外処理用の関数宣言
declare i8*  @__cxa_allocate_exception(i32) 
declare void @__cxa_throw(i8*, i8*, i8*)
declare i8*  @__cxa_begin_catch(i8 *)
declare void @__cxa_end_catch()
declare i32  @__gxx_personality_v0(...)
declare i8* @llvm.eh.exception()
declare i32 @llvm.eh.selector.i32(i8*,i8*,...)

;;; 例外送出関数
define void @throw_fn(i32 %max) {
  %n1 = call i32 @rand()
  %n2 = urem i32 %n1, %max
  %b = icmp eq i32 %n2, 0

  br i1 %b, label %OTHER, label %ZERO
ZERO:
  ret void

OTHER:
  ;; 例外用の領域を確保し、値を設定し、型情報と共に送出する
  %ex   = call i8* @__cxa_allocate_exception(i32 4) ; sizeof(int)	
  %ex32 = bitcast i8* %ex to i32*
  store i32 100, i32* %ex32
  call void @__cxa_throw(i8* %ex, i8* bitcast(%type_info* @_ZTIi to i8*), i8* null)
  ret void
}

;;; ループ
define void  @try_catch_loop(i32 %max, i32 %repeat) {
ENTRY:
  br label %LOOP

LOOP:
  %n  = phi i32 [0,%ENTRY],[%n1,%NEXT],[%n1,%INC_AND_NEXT]

  %b = icmp eq i32 %n, %repeat
  br i1 %b, label %END, label %CALL

CALL:
  %n1 = add i32 %n, 1  
  invoke void @throw_fn(i32 %max) to label %NEXT unwind label %INC_AND_NEXT
NEXT:
  br label %LOOP

INC_AND_NEXT:
  ;; 初期化と例外捕捉
  %ex = call i8* @llvm.eh.exception() 
  %id = call i32 (i8*,i8*,...)* @llvm.eh.selector.i32
          (i8* %ex, i8* bitcast(i32 (...)* @__gxx_personality_v0 to i8*), i8* null)

  ;; 送出された例外の取得と後始末
  %p = call i8* @__cxa_begin_catch(i8* %ex) 
  call void @__cxa_end_catch()             

  %t1 = load i32* @COUNTER
  %t2 = add i32 %t1, 1
  store i32 %t2, i32* @COUNTER
  br label %LOOP

END:
  ret void
}

後は比較用に、同様の処理を行うC++コードと例外処理を行わない版のコードも作成しておく。

/**
 * ファイル名: eh.cc
 * コンパイル: g++ -o eh eh.cc
 * 実行方法  : eh <生成される乱数の最大値> <ループ回数>
 *
 * [注釈]
 *  内部的にはDWARF例外処理が用いられている
 **/
#include <cstdio>
#include <cstdlib>

int g_count=0;

void throw_fn(int max) {
  if(0==rand()%max)
    throw 10;
}

void try_catch_loop(int max, int repeat) {
  for(int i=0; i < repeat; i++)
    try {
      throw_fn(max);
    } catch (...) {
      g_count++;
    }
}

int main(int argc, char** argv) {
  try_catch_loop(atoi(argv[1]), atoi(argv[2]));
  printf("%d\n",g_count);
  return 0;
}
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; ファイル名: neh.ll
;;;; コンパイル: llvm-as neh.ll -o neh.bc
;;;; 実行方法:   lli neh.bc <生成される乱数の最大値> <ループ回数>
;;;; 
;;;; [注釈]
;;;;  例外送出の代わりにbool値を返し、trueならカウンタをインクリメントする

@FMT = internal constant [4 x i8] c"%d\0A\00"
@COUNTER = internal global i32 0

declare i32 @rand()
declare i32 @atoi(i8*)
declare void @printf(i8*,i32)

define i32 @argv2int(i8** %argv,i32 %index) {
  %arg1 = getelementptr i8** %argv, i32 %index
  %a    = load i8** %arg1
  %i    = call i32 @atoi(i8* %a)
  ret i32 %i
}

define i1 @throw_fn(i32 %max) {
  %n1 = call i32 @rand()
  %n2 = urem i32 %n1, %max
  %b = icmp eq i32 %n2, 0

  br i1 %b, label %OTHER, label %ZERO
ZERO:
  ret i1 0

OTHER:
  ret i1 1
}

define void  @try_catch_loop(i32 %max, i32 %repeat) {
ENTRY:
  br label %LOOP

LOOP:
  %n  = phi i32 [0,%ENTRY],[%n1,%NEXT],[%n1,%INC_AND_NEXT]

  %b = icmp eq i32 %n, %repeat
  br i1 %b, label %END, label %CALL

CALL:
  %n1  = add i32 %n, 1  
  %ret = call i1 @throw_fn(i32 %max)
  br i1 %ret, label %NEXT, label %INC_AND_NEXT       
  
NEXT:
  br label %LOOP

INC_AND_NEXT:
  %t1 = load i32* @COUNTER
  %t2 = add i32 %t1, 1
  store i32 %t2, i32* @COUNTER
  br label %LOOP

END:
  ret void
}

define i32 @main(i32 %argc, i8** %argv) {
  %max    = call i32 @argv2int(i8** %argv, i32 1)
  %repeat = call i32 @argv2int(i8** %argv, i32 2)

  call void @try_catch_loop(i32 %max, i32 %repeat)
  %throw_cnt = load i32* @COUNTER
  
  call void @printf(i8* getelementptr([4 x i8]* @FMT, i32 0, i32 0) ,i32 %throw_cnt)
  ret i32 0
}

計時

計時。
条件を揃えていないし、正確なものではないが、ごくおおまかな特徴くらいは分かる(かもれしれない)

####
## ほとんど例外が発生しない場合の処理速度 
$ time lli unwind.bc 100000000 100000000   # invoke/unwind
1                 # <- 例外発生数
real	0m2.074s
user	0m2.076s
sys	0m0.000s

$ time ./dwarf 100000000 100000000         # dwarf
1
real	0m1.863s
user	0m1.848s
sys	0m0.012s

$ time ./eh 100000000 100000000            # C++
1
real	0m2.204s
user	0m2.204s
sys	0m0.000s

$ time lli neh.bc 100000000 100000000      # 例外なし
1
real	0m1.943s
user	0m1.940s
sys	0m0.004s

####
## 例外が頻発する(という例外的な)ケースでの処理速度
$ time lli unwind.bc 100 100000000 
998931
real	0m2.196s
user	0m2.188s
sys	0m0.004s

$ time ./dwarf 100 100000000 
998931
real	0m6.017s
user	0m6.008s
sys	0m0.008s

$ time ./eh 100 100000000 
998931
real	0m6.229s
user	0m6.224s
sys	0m0.004s

$ time lli neh.bc 100 100000000 
998931
real	0m1.970s
user	0m1.964s
sys	0m0.004s

*1:Exception Handling in LLVM — LLVM 3.4 documentation

*2:the invoke/unwind semantics are likely to change in future versions.LLVM Language Reference Manual — LLVM 3.4 documentation

*3:自分の環境のgccがどちらに対応しているかは、`gcc -v`コマンドで確認可能。--enable-sjlj-exceptionsという文字列が出力に含まれていた場合は、setjump/longjump例外処理に対応している。