今回も会場を提供してustream中継をしてくださった@kzmogiさん, @lunatic_startさんと(株)AXELL社のご好意に感謝します. 発表者の方もありがとうございました.
とりあえず資料へのリンク(upされしだい順次追加します).
Power Pointでやり直し回数を増やす
Power Pointで資料を作るとき, うっかりデータを削除してしまって元に戻そうとしてもちょっとしか戻ってくれなくて困ったことがあったのだが, 今日増やせることを知った. これから全部のやつに設定するためにメモしておく.
[ファイル]→[オプション]→[詳細設定]→[元に戻す操作の最大数]を150(限界)にできる. 初期値はたった20か. 少ないな.
Xbyakでラベルが指すアドレスをmovでレジスタに入れたい
@miura1729さんの依頼で対応. 実は私自身今まで何度かそれが欲しいケースがあって対応しようとしてたのだけど思ったよりややこしくて毎回断念してた. 今回は外部の要求なので一念発起で対応することにした. できるようになりたいことは次の通り:
L("lp1");
mov(eax, "lp1");
jmp(eax); // lp1に飛ぶ
mov(eax, "lp2");
jmp(eax); // lp2に飛ぶ
L("lp2);
見た目はどうってことないのに, これのどこがややこしかったかというと, 内部的にはラベルが定義されているとされていない, 絶対jmpと相対jmp, fixモードとautoGrowモードの組み合わせがあって, ラベルを参照するときと定義するときにそれぞれのケースで処理を変えないといけなかったから.
fixモードは与えられた領域にコードを生成しているときで, アドレス計算などに必要な値は決定されているので比較的容易. autoGrowモードはメモリが足りなくなったらそれまで生成したコードをごそっと移動するのでラベルのアドレスが変わる. 最終的にready()が呼ばれたときに再計算する必要がある.
もちろん, 普通のアセンブラはそんなことをやってるのだがXbyakはもともとfixモードしかなくて, かつコード生成が完了したことを示すready()関数を呼ばずに使いたいという仕様にしていた. 「ready()を呼ばない」という縛りが意外ときつくて内部的にごちゃごちゃになってしまった.
まあなんとか動くようになったのだが, 今回はテストパターンを作るのも面倒だった. 64bitだとアドレスは8byte確保しておいて確定した段階でそこを埋めるのだけど, たまたまオフセットが4byteに納まるとmov()命令生成内部で勝手に4byte + zero拡張のモードにしてしまってずれちゃったり.
こんなの世の中の巨大で複雑なアプリに比べたらどうってことはない些細なことだろうけど久しぶりに頭使った.
第３回神保町暗号ワークショップ「ＣＢＣモードの現在（いま）～ＣＢＣモードに何が起こっているか？」に参加
少し前に話題になったBEAST攻撃, CRIME攻撃や最近発表された新しい攻撃についての解説. padding oracleの考え方, CBCモードの構造などの基本的なところから初めてその脅威や対応方法について教わった.
「で, 結局(サーバは)どう設定したらいいの?」という研究者じゃない大多数の人が思う疑問に対して, 研究者や国の機関は現状どう対応しているのか, 今後どう伝えていくかという議論もあった.
とてもすばらしいワークショップだった. 発表者, 主催者の方どうもありがとうございました.
発表資料を上記サイトから取得できるとありがたいな.
fmindex++のWavelet matrixクラスを入れ換えてみる
田部井さん(@tb_yasu)FM-index++はFM-indexを使った検索ライブラリ. これはWavelet treeライブラリwat-arrayのLookup(=get)とRankしか使っていない. だから今作ってる途中のWavelet matrixクラスcybozu/wavelet_matrix.hppに簡単に置き換えることができるだろうと実験してみた.
ついでに真鍋さんのwavelet-matrix-cppとの比較もしてみた. なお, 以下のベンチマークでは適当にやったのものなのでどの程度信用できるかわかりません. 「こういうデータでやるべき」というのがありましたら教えてくださるとありがたいです.
やったこと : fmindex++のwat_arrayをwavelet_matrix::WaveletMatrixやcybozu::WaveletMatrixに置き換えて, search.cppを実行して時間を測る. 出力結果a.txt(約220MB)はどれでやっても完全一致した.
環境はXeon X5650 2.7GHz@ubuntu 12.04 LTS, gcc 4.6.3. 実験コードはhttps://github.com/herumi/fmindex.
input.txt : 入力データ(約200MBの日本語UTF-8テキスト) query.txt : クエリデータ(1400個の適当な日本語, 英語の単語) ./construct input.txt input.data time ./search input.data query.txt > a.txt
| 実装 | 時間[sec] | lookup[clk] | rank[clk] |
|---|---|---|---|
| オリジナル | 160 | 1887 | 1887 |
| wavelet-matrix-cpp | 72 | 883 | 598 |
| cybozu/waveletmatrix | 30 | 343 | 183 |
単純ベンチマークでオリジナルの5.3倍, wavelet-matrix-cppに比べても2.5倍速くなった.
実行時に関数が呼ばれた回数はlookupで145425984回, rankで72730872だった. それぞれの関数にかかったクロック数を見ると概ねlookupの性能が表に出ているようだ.
これとは別にwm_test.cppではランダムデータに対するgetやrankのベンチマークをとっていた. その結果はこちら.
| 実装 | lookup | rank | rank_less_than | select |
|---|---|---|---|---|
| wat-array | 2.01(5427) | 2.25(6075) | 2.25(6075) | 10.31(27837) |
| wavelet-matrix-cpp | 1.38(3726) | 1.62(4374) | 1.64(4428) | 5.92(15984) |
| cybozu/waveletmatrix | 0.94(2538) | 0.94(2538) | 1.03(2781) | 4.71(12717) |
上記ベンチマークとスコアが全然違う. どれも実際のテキストでやった場合の方がずっと速い. ライブラリ間のlookupの性能差はsearchの中での値よりも小さい. キャッシュヒットのし易さやビットパターンの傾向が違うからだろうか. もっと大きいファイルで試すと差は小さくなるのかな.
流石にここまで違うと最適化の指標として扱いにくい. cybozu/waveletmatrixが速いのは確かなようだが, 他の方がやってる測定方法でも試してみて原因を探さないとあかんな.
メガネのフレームが折れたので1回休み.
うーん, アロンアルファでくっつけようとしたけど無理だ. 流石にこれは買いに行かないとどうしようもない. プリンタも壊れてしまったし, 買物しないといかんのが多いな.
最近疲れて9時過ぎに寝てしまって, すると明け方4時頃目が覚めてしまうのでおもむろにLLVMのことを調べて, いつのまにか朝の8時とかで, ああ会社だ, でも今日は在宅勤務にしたからそのまま仕事しようという感じが続いていたので今日がいつだか分からない. ああ, 昨日は休みだった.
ていうかx86/x64最適化勉強会5まであと9日か. スライド準備しないと. LLVM入門というセッションも作るか. 間に合うかな.
LLVM手習い その6 SDNodeをいじってみる(保留)
19日の続き. llcが落ちてる箇所はCodeGen/SelectionDAG/LegalizeIntegerTypes.cpp のDAGTypeLegalizer::PromoteIntegerResult(). これは整数拡張のところで呼ばれるようだ. i1を符号拡張も符号なし拡張もしないで使おうとして怒られたのだろうか(自信なし).
ただ考えてみればi1という1bitでは情報が足りない. 当たり前だが単なる1bitではなくADDC/SUBC/ADDE/SUBEによってえられたcarryの1bitを渡さないといけないのだ. というわけでマッチさせるべきは
// 間違い ADD (ADD (x, zeroExt(1bit)), y) -> ADDE (x, y, 1bit) // OK? ADD (ADD (x, zeroExt(extract CF flag of ADDC/SUBC/ADDE/SUBE)), y) -> ADDE (x, y, CF)
みたいな感じだろうか. しかしそこそこ長いツリーをたどったマッチングをしないといけない. できたとしても面倒だし, 本当にマッチするのか分からない.
そもそもADDEを生成すべきなのをばらして作ってあとで(最適化で)くっつけようというのは筋が悪い気がする. 19日でLLVMがcarryの伝搬に四苦八苦してるのもそのせいじゃないかなあ.
とか思ってたら@kazegusuriさんも「フラグの扱いが少し面倒ですね」と書かれていた. というわけでこれがやりたいことじゃないので一端ペンディングにしよう.
まあ少しだけLLVMの中身を見てわかったのはコードがとてもきれいだということだ. 感嘆した. こんな巨大なソースコードを初心者が数時間みただけで少しはいじれるというのはたいしたものだと思う.
LLVM手習い その5 SDNodeをいじってみる(途中経過)
17日の日記で「adc + addがadcにならない」と書いていたら, @kazegusuriさんがSDNodeのパターンマッチするだけと仰ってたので試してみる.
まずllvmのソースの中からSDNodeを探す. lib/CodeGen/SelectionDAG/DAGCombiner.cppにいろいろ書かれている. 中を見ると
// fold (A+(B-(A+C))) to (B-C) ... // fold ((c1-A)+c2) -> (c1+c2)-A ... // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n)) ...
みたいな感じで様々な特殊ケースの最適化をやってる. ならここをいじればよいのだろう.
include/llvm/CodeGen/ISDOpcodes.hを見るとLLVMではADDは2項演算, ADDCが2項演算で出力がcarryつき, ADDEがcarryつき3項演算とのこと. 内部でADDEを持ってるならそれを外に出してくれればいいのに.
それはともかく今やりたいことは擬似的に書くと
ADD (ADD (x, zeroExt(CF)), y) -> ADDE (x, y, CF)
かな. とりあえず見よう見まねでDAGCombiner::visitADD()に追加してみよう. 対象としているツリーのノードはSDNode *NでそのオペランドはgetOperandで取れるようだ.
SDValue DAGCombiner::visitADD(SDNode *N) {
SDValue N0 = N->getOperand(0);
SDValue N1 = N->getOperand(1);
一つ目の引数がADDでそのADDの二つ目の引数がzeroExtなら引っかけるのでこう書いてみた.
// N0 N1
// add (add (x, zext i1)), y -> adc (x, y, i1)
// 一つ目の引数がadd
if (N0.getOpcode() == ISD::ADD) {
// そのaddの二つ目の引数がzext
if (N0.getOperand(1).getOpcode() == ISD::ZERO_EXTEND) {
// そのzextの引数が1bitなら
if (N0.getOperand(1).getOperand(0).getValueType() == MVT::i1) {
// 変換を書く
}
}
}
まず変換のところでadcではなく単なるaddにしてみる.
// x y return DAG.getNode(ISD::ADD, N->getDebugLoc(), VT, N0.getOperand(0), N1);
すると
adcq $0, %rax addq 8(%rdx), %rax
だった出力が
addq 8(%rdx), %rax
になった. adcの情報を捨てたのだから当然だけどこのパスが通ってることは確認できた. ではISD::ADDEにして3番目の引数にzext i1であるN0.getOperand(1)を渡してみよう.
return DAG.getNode(ISD::ADDE, N->getDebugLoc(), VT, N0.getOperand(0), N1, N0.getOperand(1));
出力結果はこうなった.
movq (%rsi), %rax
addq (%rdx), %rax
movq %rax, (%rdi)
;***
sbbq %rax, %rax ; rax = CF ? -1 : 0
andq $1, %rax ; rax = CF ? 1 : 0
movq 8(%rsi), %rcx
pushq %rax ; flag
popfq ; CF = flag
;***
adcq 8(%rdx), %rcx
ret
おお, addがまとめられて最後のadcqになった. なったはよいがcarryを伝搬させるためにえらい苦労している(泣). ***でくくった部分は丸ごと要らないのだが.
zextしてから渡してるのでそうなってるのだろうか. もともとのcarryはN0.getOperand(1).getOperand(0)で取れそうだからそれを渡してみよう(実際, このifに突入したということはそういうことだろう).
return DAG.getNode(ISD::ADDE, N->getDebugLoc(), VT, N0.getOperand(0), N1, N0.getOperand(1).getOperand(0));
ところがこうするとllcが落ちるようになってしまった.
Do not know how to promote this operator's operand! UNREACHABLE executed at /home/shigeo/soft/clang/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp:763! 0 llc 0x00000000014e716e llvm::sys::PrintStackTrace(_IO_FILE*) + 46 1 llc 0x00000000014e742b 2 llc 0x00000000014e768a 3 libpthread.so.0 0x00007f75bec57cb0 4 libc.so.6 0x00007f75bdca1425 gsignal + 53 5 libc.so.6 0x00007f75bdca4b8b abort + 379 6 llc 0x00000000014cc4e6 7 llc 0x0000000000dc38af 8 llc 0x0000000000d84edb 9 llc 0x0000000000d89c1e llvm::SelectionDAG::LegalizeTypes() + 46 10 llc 0x0000000000d259b7 llvm::SelectionDAGISel::CodeGenAndEmitDAG() + 1063
さてどうしよう.
LLVM手習い その4 基本的なループ
17日の「adcが無い問題」は@nothingcosmosさんによると「現状無い」とのこと. intrinsicや既存のC/C++ではできなかったcarryの制御をうまく扱えそうにみえたのに残念な仕様だ.
それはさておき, ループのやり方を勉強してみる. 単純なsum関数を作ってみよう.
uint64_t sum64(const uint64_t *x, uint64_t n)
{
uint64_t ret = 0;
for (uint64_t i = 0; i < n; i++) {
ret += x[i];
}
return ret;
}
SSAなのでループの中で変数の値を更新することができない. そのためループ変数と累積変数retの値をphiを使って参照する.
define i64 @sum64(i64* nocapture %x, i64 %n) {
entry:
%n_is_0 = icmp eq i64 %n, 0
br i1 %n_is_0, label %exit, label %lp
lp:
%i_p = phi i64 [ %i, %lp ], [ 0, %entry ]
%ret_p = phi i64 [ %ret, %lp ], [ 0, %entry ]
%x_i = getelementptr inbounds i64* %x, i64 %i_p
%v = load i64* %x_i, align 64
%ret = add i64 %ret_p, %v
%i = add i64 %i_p, 1
%i_eq_n = icmp eq i64 %i, %n
br i1 %i_eq_n, label %exit, label %lp
exit:
%r = phi i64 [ 0, %entry ], [ %ret, %lp ]
ret i64 %r
}
まずnが0なら抜ける. そうでないならループに突入. i_p, ret_pはentryから来た場合は初期値0でそうでない場合はiやretの値とする.
phiを使わずに
%ret = add i64 %ret, %v
とするとOnly PHI nodes may reference their own value!と怒られる.
次に参照すべきポインタの位置をgetelementptrで求める. そこから値vを取り出してretに加算する. iを1増やしてnになるまでループする. これを変換するとこうなった.
sum64:
xor EAX, EAX
test RSI, RSI
je .exit
.align 16, 0x90
.lp:
add RAX, QWORD PTR [RDI]
add RDI, 8
dec RSI
jne .lp
.exit:
ret
ループ変数が0からnではなくnから0に向かってdec + jneに変換された. ついでにi64をi32にするとループ変数が素直なパターンになるのだな. ecxは符号なし32bitなつもりだがmovsxdで符号拡張されている. なんでかな. どこかにアノテーションがいるのかな.
sum32:
xor ECX, ECX
xor EAX, EAX
test ESI, ESI
je .exit
.align 16, 0x90
.lp:
movsxd RCX, ECX
add EAX, DWORD PTR [RDI + 4*RCX]
inc ECX
cmp ESI, ECX
jne .lp
.exit:
ret
ついでにarmでもコメントをつけながら読んでみよう. armはオペランドの順がIntel asmと同じなのね.
sum32:
// r0 = x, r1 = n
mov r2, r0 // r2 = x
mov r0, #0 // r0 = 0
cmp r1, #0
moveq pc, lr // n == 0ならpc = lrしてreturn
.lp:
ldr r3, [r2], #4 // r3 = *r2, r2 += 4
subs r1, r1, #1 // r1--, 条件フラグ変更
add r0, r0, r3 // r0 += r3
bne .lp // r1 != 0ならループ
mov pc, lr
命令の後ろにsをつけると条件フラグを更新するらしい. bneはsubsに対応する. addだとフラグを更新しないのか.
LLVM手習い その3 carryを扱ってみる.
二つのuint32_tを足して結果がoverflowしたらtrueを返す関数を作ろう.
// *z = x + y
// return true if overflow
// bool add_over(uint32_t *z, uint32_t x, uint32_t y);
declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)
define zeroext i1 @add_over(i32* %z, i32 %x, i32 %y)
{
entry:
%0 = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)
%ret = extractvalue { i32, i1 } %0, 0
store i32 %ret, i32* %z
%flag = extractvalue { i32, i1 } %0, 1
ret i1 %flag
}
llvm.uadd.with.overflow.i32という組み込み関数があるのでそれを使う. この関数の戻り値は{i32,i1}という32bitの値と1bitのflagのペアである. 個別の要素の値を取り出すにはextractvalueを使う.
組み込み関数だけど, 冒頭のようにdeclareしないとundefined valueと言われてしまった.
// 結果
add_over:
addl %edx, %esi
movl %esi, (%rdi)
setb %al
ret
@kazuhoさんのwriting-fast-code-using-c-llvm-bitcodeでは引数を一度allocaしてstoreしていたがしなくてもよさそう. 生成x64コードは同一だった.
carryを扱えるようになったので16日のadd3をi128を使わずに作ってみよう. というところで困った. マニュアルにはcarryを伴うadd(adc)が見当たらない. とりあえあずフラグも加算するコードを書いてみよう.
declare { i64, i1 } @llvm.uadd.with.overflow.i64(i64, i64)
define void @add4(i64* %z, i64* %x, i64* %y)
{
entry:
%xL = load i64* %x, align 64
%yL = load i64* %y, align 64
%0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %xL, i64 %yL)
%zL = extractvalue { i64, i1 } %0, 0
store i64 %zL, i64* %z
%flag = extractvalue { i64, i1 } %0, 1
%flagExt = zext i1 %flag to i64
%pxH = getelementptr i64* %x, i64 1
%pyH = getelementptr i64* %y, i64 1
%pzH = getelementptr i64* %z, i64 1
%xH = load i64* %pxH, align 64
%yH = load i64* %pyH, align 64
%zH = add i64 %xH, %flagExt
%zH2 = add i64 %zH, %yH
store i64 %zH2, i64* %pzH
ret void
}
まずxL = x[0], yL = y[0]を読みaddした結果からextractvalueでzLを取り出しz[0]に書き込む. flagも取り出してzextでi64にゼロ拡張しておく.
次にgetelementptrを使ってpxH = x + 1, pyH = y + 1, pzH = z + 1を求める. xH = *pxH, yH = *pyHとして加算する. ゼロ拡張したflagExtとyHをxHに足してpzHに保存する. 結果はこうなった.
add4:
movq (%rsi), %rax
addq (%rdx), %rax
movq %rax, (%rdi)
movq 8(%rsi), %rax
adcq $0, %rax ; *
addq 8(%rdx), %rax ; *
movq %rax, 8(%rdi)
ret
うーん, *の部分が合成されてadcq 8(%rdx), %raxになって欲しい. というかやっぱり直接adcを使いたい. Add/sub with carryでadc命令が欲しいという話題が出てる(2007年)が入ってない. 多分別のやり方があるのだろう. どうするのかな.
@llvm.x86.sse42.pcmpistri128みたいなx86固有の命令を呼び出す方法もあるようだ(adcでそれがあるのか分からない. 組み込み一覧リストはどこ?). もちろんx86固有命令の呼び出しは-march=armしたらエラーになった.
LLVM手習い その2
メモリにアクセスしてみる. 次のadd3関数を作ってみよう.
void add3(uint64_t *z, const uint64_t *x, const uint64_t *y)
{
*z = *x + *y;
}
define void @add3(i64* %z, i64* %x, i64* %y) {
entry:
%0 = load i64* %x, align 64
%1 = load i64* %y, align 64
%2 = add i64 %0, %1
store i64 %2, i64* %z, align 64
ret void
}
これを変換するとx64, x86, armで次のようになった.
// x64
add3:
mov rax, qword [rdx]
add rax, qword [rsi]
mov qword [rdi], rax
ret
// x86
add3:
mov ecx, dword [esp + 12] ; y
mov eax, dword [ecx] ; y[0]
mov ecx, dword [ecx + 4] ; y[1]
mov edx, dword [esp + 8] ; x
add eax, dword [edx] ; y[0] + x[0]
adc ecx, dword [edx + 4] ; y[1] + x[1] + carry
mov edx, dword [esp + 4] ; z
mov dword [edx + 4], ecx ; z[1]
mov dword [edx], eax ; z[0]
ret
// arm
add3:
ldm r1, {r3, r12}
ldm r2, {r1, r2}
adds r1, r1, r3
adc r2, r2, r12
stm r0, {r1, r2}
mov pc, lr
x64, x86は最適なコードに変換されている. armはちょっとわからないけどaddsとadcがあるので多分最適なんだろう. すばらしい. 調子に乗ってu128的な加算を作ってみよう.
// 擬似コード
void add3(uint64_t *z, const uint64_t *x, const uint64_t *y)
{
z[0] = x[0] + y[0];
z[1] = x[1] + y[1] + with carry;
}
単にloadの部分をi128にすると型エラーになってしまう.
define void @add3(i64* %z, i64* %x, i64* %y) {
entry:
%0 = load i128* %x, align 64
%1 = load i128* %y, align 64
%2 = add i128 %0, %1
store i128 %2, i64* %z, align 64
ret void
}
llc: test0.ll:62:18: error: '%x' defined with type 'i64*'
%0 = load i128* %x, align 64
そこでbitcast命令を使って強引にアクセスしてみる.
define void @add3(i64* %z, i64* %x, i64* %y) {
entry:
%0 = bitcast i64* %x to i128*
%1 = bitcast i64* %y to i128*
%2 = load i128* %0, align 64
%3 = load i128* %1, align 64
%4 = add i128 %2, %3
%5 = bitcast i64* %z to i128*
store i128 %4, i128* %5, align 64
ret void
}
add3:
mov rax, qword [rsi]
mov rcx, qword [rsi + 8]
add rax, qword [rdx]
adc rcx, qword [rdx + 8]
mov qword [rdi + 8], rcx
mov qword [rdi], rax
ret
おお, ちゃんと望みのコードが生成された. x86だとaddが1個, adcが3個の命令に変換されていることが確認できる. i128をi256にしたらuint256_t相当のコードになった. 全くもってすばらしい.
LLVM手習い
マニュアルはLLVM Language Reference Manual.
CのコードをLLVMアセンブラにするには-emit-llvmを使う.
>cat t.c
int add1(int x, int y)
{
return x + y;
}
unsigned int add2(unsigned int x, unsigned int y)
{
return x + y;
}
>clang -S -O3 -emit-llvm t.c -o -
define i32 @add1(i32 %x, i32 %y) #0 {
entry:
%add = add nsw i32 %y, %x
ret i32 %add
}
define i32 @add2(i32 %x, i32 %y) #0 {
entry:
%add = add i32 %y, %x
ret i32 %add
}
いろんな箇所に変数の型を表すi32がついてる. intの足し算についてるnswはno singed wrapという意味. ついてると結果の値はPoison Valueというのになるらしい. なんかよくわからんがCの規格でintの足し算がオーバーフローしたときは処理系依存なので印がついてるのだろう.
llc test0.ll -o -でLLVMのアセンブラをネイティブの環境のアセンブラコードに変換する.
>cat test0.ll
define i32 @add1(i32 %x, i32 %y) {
entry:
%0 = add i32 %x, %y
ret i32 %0
}
add1: # @add1
leal (%rdi,%rsi), %eax
ret
この時点でaddがleaになるなどの最適化がおこなわれている. mul x, 8もshl x, 3になったりしてた. -march=x86とすると32bitモード. -x86-asm-syntax=intelならIntel形式で出力. 便利だな.
add1: # @add1
mov EAX, DWORD PTR [ESP + 4]
add EAX, DWORD PTR [ESP + 8]
ret
-march=armとするとarmのコードを生成する. サポートしてるターゲットはllc --versionで表示される.
; arm
add1: @ @add1
add r0, r0, r1
mov pc, lr
armはreturnの代わりにpcに値を設定するようだ.
最大値をとる関数を書いてみる.
define i32 @my_max2(i32 %x, i32 %y) {
entry:
%cmp = icmp ugt i32 %x, %y
br i1 %cmp, label %x_gt_y, label %otherwise
x_gt_y:
ret i32 %x
otherwise:
ret i32 %y
}
xとyをunsignedで比較して大なり(greater than)でとるのでicmp ugtとする. br i1のi1は1bitの整数らしい. 条件が成立したときと成立しなかったときのラベルを記述する. llcをかけるとこうなった.
my_max2:
cmpl %esi, %edi
jbe .LBB4_2
movl %edi, %eax
ret
.LBB4_2:
movl %esi, %eax
ret
ラベルが二つあるからと言ってどちらでもジャンプするわけじゃない. それぞれでretじゃなくて処理を続けたいときはphiを使う. LLVMはSSA(静的単一代入形式)なので制御の合流が必要.
define i32 @my_max(i32 %x, i32 %y) {
entry:
%cmp = icmp ugt i32 %x, %y
br i1 %cmp, label %x_gt_y, label %otherwise
x_gt_y:
%0 = add i32 %x, 0
br label %exit
otherwise:
%1 = add i32 %y, 0
br label %exit
exit:
%cond = phi i32 [ %0, %x_gt_y ], [ %1, %otherwise ]
ret i32 %cond
}
%0 = add i32 %x, 0なんて無駄なaddをしてるが単なるアサインをどう書いていいのかわからなかっただけ. 多分ちゃんとした書き方があると思う. ただこのコードはmovになっていたので特に問題ないのかも.
my_max:
cmpl %esi, %edi
ja .LBB3_2
movl %esi, %edi
.LBB3_2:
movl %edi, %eax
ret
armだとこうなった. エレガント.
my_max:
cmp r0, r1
movls r0, r1
mov pc, lr
やっちまったその1
あまりに足が痛いので病院に行って問診票に「左足が痛い」と書いて診察するときに足を見せる段になって気がついた. 「ああ, 痛いの右足です.」 なんかどうも左右をよく間違える(下の日記でも間違えている).
やっちまったその2
LinuxのDRBDでdiskパラメータに指定したファイル(バッキングファイル)を別のプロセスから取得したくて, sysfsで取得するdriverのpatchを作ってMLに投げてみたら, それdrbdsetup showでできるよという返事. なぜ気がつけなかったのだろう. 相当恥ずかしい.
先週, 左脚が酷くつって痛くてかばって歩いているせいか土踏まずや足の甲も痛くなってきてしかたがない. 歩くのも難儀.
ここしばらくate-pairingに対する使い方の質問が立て続けにあった.
現状がだれだって使い方を間違えるだろうという中途半端で酷いAPIだったので, えいやと整理した. だいぶ使いやすい形になったんじゃなかろうか. 最近はペアリングを使った応用プロトコルもいろいろあるので実験するのも面白いと思う. こんな感じ.
using namespace bn;
Param::init();// init my library
const Ec2 g2(Fp2(...));
const Ec1 g1(Fp(...));
Fp12 e;
// calc e : G2 x G1 -> G3 pairing
opt_atePairing(e, g2, g1);
mpz_class a("1234567989242424");
mpz_class b("1234943fa234567989242424");
Ec1 g1a = g1 * a;
Ec2 g2b = g2 * b;
Fp12 eba;
// calc eba : G2 x G1 -> G3 pairing
opt_atePairing(eba, g2b, g1a);
printf("%s\n", eba == power(e, a * b) ? "ok" : "ng");
シャベルとスコップ
豪雪の事故の新聞記事で「車を掘り出すのにスコップを使った」という見出しがあって, それは流石に非力過ぎるだろと思ったのだが写真を見て気がついた.
シャベルとスコップって人によって意味が違うんだな.
私にとってスコップはこどもが砂場で遊ぶときに使う, 手で持つ小さいやつで, シャベルは工事現場などで使う, 足で押しつけながら地面を掘る1mぐらいの大きいやつ.
検索してみると関西では私と同じで関東では逆のことが多いらしい. そういえば以前知人に教えてもらって「へー」と思ったような気もするけど, 実際に取り違えに気がついたのは初めてだ.
約9カ月振りにx86/x64最適化勉強会5を開催しようと思います。 前回は2012/6/16でした。 今回はx86/x64しばりを外してARMもOKです。ただいま発表者募集中です。
私自身はARMのことはほとんど知らないので勉強会で強制的に調べるメソッドを発動させよう。