hotspot/src/cpu/sparc/vm/templateTable_sparc.cpp
void TemplateTable::fast_binaryswitch() {
{- -------------------------------------------
(1) (assert) (See: TemplateTable::transition())
---------------------------------------- -}
transition(itos, vtos);
{- -------------------------------------------
(1) (この関数が生成するコードは以下の二分探索アルゴリズムを実行する)
---------------------------------------- -}
// Implementation using the following core algorithm: (copied from Intel)
//
// int binary_search(int key, LookupswitchPair* array, int n) {
// // Binary search according to "Methodik des Programmierens" by
// // Edsger W. Dijkstra and W.H.J. Feijen, Addison Wesley Germany 1985.
// int i = 0;
// int j = n;
// while (i+1 < j) {
// // invariant P: 0 <= i < j <= n and (a[i] <= key < a[j] or Q)
// // with Q: for all i: 0 <= i < n: key < a[i]
// // where a stands for the array and assuming that the (inexisting)
// // element a[n] is infinitely big.
// int h = (i + j) >> 1;
// // i < h < j
// if (key < array[h].fast_match()) {
// j = h;
// } else {
// i = h;
// }
// }
// // R: a[i] <= key < a[i+1] or Q
// // (i.e., if key is within array, i is the correct index)
// return i;
// }
{- -------------------------------------------
(1) (変数宣言など) &(assert)
---------------------------------------- -}
// register allocation
assert(Otos_i == O0, "alias checking");
const Register Rkey = Otos_i; // already set (tosca)
const Register Rarray = O1;
const Register Ri = O2;
const Register Rj = O3;
const Register Rh = O4;
const Register Rscratch = O5;
const int log_entry_size = 3;
const int entry_size = 1 << log_entry_size;
Label found;
{- -------------------------------------------
(1) コード生成:
「現在の Lbcp から 13bytes 以上先で 4bytes-align なアドレス(= match-offset pairs 情報の先頭)を算出し,
Rarray レジスタにセットする」
(13byte は, _fast_binaryswitch 命令自体が 1byte 占めているため)
---------------------------------------- -}
// Find Array start
__ add(Lbcp, 3 * BytesPerInt, Rarray);
__ and3(Rarray, -BytesPerInt, Rarray);
{- -------------------------------------------
(1) コード生成:
「Ri レジスタを 0 で初期化しておく」
---------------------------------------- -}
// initialize i & j (in delay slot)
__ clr( Ri );
{- -------------------------------------------
(1) コード生成:
「Rj レジスタをペアの個数で初期化した状態で,
entry ラベルにジャンプして探索を開始する」
---------------------------------------- -}
// and start
Label entry;
__ ba(false, entry);
__ delayed()->ld( Rarray, -BytesPerInt, Rj);
// (Rj is already in the native byte-ordering.)
{- -------------------------------------------
(1) (ここからが, 該当するエントリを探索するループ)
---------------------------------------- -}
// binary search loop
{ Label loop;
{- -------------------------------------------
(1.1) コード生成:
「(ここが loop ラベルの位置)」
---------------------------------------- -}
__ bind( loop );
{- -------------------------------------------
(1.1) コード生成:
「Rh レジスタの値を半分にする (この時点で Rh = (Ri + Rj) >> 1 になる)」
---------------------------------------- -}
// int h = (i + j) >> 1;
__ sra( Rh, 1, Rh );
{- -------------------------------------------
(1.1) コード生成:
「Rh レジスタが指す箇所のペアのキーをロードし, 対象のキーの値(Rkey)と比較する.
Rkey の方が小さければ Rj を Rh で更新し, そうでなければ Ri を Rh で更新する.」
(なおこの処理は, SPARCv9 以降なら conditional move で行っている)
---------------------------------------- -}
// if (key < array[h].fast_match()) {
// j = h;
// } else {
// i = h;
// }
__ sll( Rh, log_entry_size, Rscratch );
__ ld( Rarray, Rscratch, Rscratch );
// (Rscratch is already in the native byte-ordering.)
__ cmp( Rkey, Rscratch );
if ( VM_Version::v9_instructions_work() ) {
__ movcc( Assembler::less, false, Assembler::icc, Rh, Rj ); // j = h if (key < array[h].fast_match())
__ movcc( Assembler::greaterEqual, false, Assembler::icc, Rh, Ri ); // i = h if (key >= array[h].fast_match())
}
else {
Label end_of_if;
__ br( Assembler::less, true, Assembler::pt, end_of_if );
__ delayed()->mov( Rh, Rj ); // if (<) Rj = Rh
__ mov( Rh, Ri ); // else i = h
__ bind(end_of_if); // }
}
{- -------------------------------------------
(1.1) コード生成:
「(ここが entry ラベルの位置)」
「まだ残りがあるかどうかを調べるために, Ri + 1 が Rj より小さいかどうかを調べる.
小さければ(= まだ残りがあれば), Rh レジスタを Ri + Rj にセットして, loop ラベルに分岐.
もうペアがなければこのままフォールスルー」
---------------------------------------- -}
// while (i+1 < j)
__ bind( entry );
__ add( Ri, 1, Rscratch );
__ cmp(Rscratch, Rj);
__ br( Assembler::less, true, Assembler::pt, loop );
__ delayed()->add( Ri, Rj, Rh ); // start h = i + j >> 1;
}
{- -------------------------------------------
(1) (ここまでで, 該当するエントリを探索するループは終了.
結果は Ri に入っているが, 見つかったとは限らないのでチェックが必要)
---------------------------------------- -}
// end of binary search, result index is i (must check again!)
{- -------------------------------------------
(1) (変数宣言など)
---------------------------------------- -}
Label default_case;
Label continue_execution;
{- -------------------------------------------
(1)
---------------------------------------- -}
if (ProfileInterpreter) {
__ mov( Ri, Rh ); // Save index in i for profiling
}
{- -------------------------------------------
(1) コード生成:
「Ri レジスタが指す箇所のペアのキーをロードし, 対象のキーの値(Rkey)と比較する.
一致しない場合は, (探索対象が見つからなかったので) default_case ラベルに分岐.
(なお, 一致しなかった場合には,
遅延スロットのロード命令により, デフォルトのオフセットが Rj にセットされる)」
---------------------------------------- -}
__ sll( Ri, log_entry_size, Ri );
__ ld( Rarray, Ri, Rscratch );
// (Rscratch is already in the native byte-ordering.)
__ cmp( Rkey, Rscratch );
__ br( Assembler::notEqual, true, Assembler::pn, default_case );
__ delayed()->ld( Rarray, -2 * BytesPerInt, Rj ); // load default offset -> j
{- -------------------------------------------
(1) (以下は, 一致するペアが見つかった場合の処理)
---------------------------------------- -}
// entry found -> j = offset
{- -------------------------------------------
(1.1)
---------------------------------------- -}
__ inc( Ri, BytesPerInt );
{- -------------------------------------------
(1.1) コード生成: (JIT コンパイラ用のプロファイル情報の取得) (See: [here](no2935fdD.html) for details)
---------------------------------------- -}
__ profile_switch_case(Rh, Rj, Rscratch, Rkey);
{- -------------------------------------------
(1.1) コード生成:
「見つかったペアにおけるジャンプ先オフセットを Rj レジスタにロードしておく」
---------------------------------------- -}
__ ld( Rarray, Ri, Rj );
// (Rj is already in the native byte-ordering.)
{- -------------------------------------------
(1) コード生成: (JIT コンパイラ用のプロファイル情報の取得) (See: [here](no2935fdD.html) for details)
「continue_execution ラベルまで飛ぶことで,
ペアが見つからなかった場合のプロファイル情報取得処理を実行してしまわないようにする」
---------------------------------------- -}
if (ProfileInterpreter) {
__ ba(false, continue_execution);
__ delayed()->nop();
}
{- -------------------------------------------
(1) (以下は, 一致するペアが見つからなかった場合の処理)
---------------------------------------- -}
__ bind(default_case); // fall through (if not profiling)
{- -------------------------------------------
(1.1) コード生成: (JIT コンパイラ用のプロファイル情報の取得) (See: [here](no2935fdD.html) for details)
---------------------------------------- -}
__ profile_switch_default(Ri);
{- -------------------------------------------
(1) コード生成:
「(ここが continue_execution ラベルの位置)」
---------------------------------------- -}
__ bind(continue_execution);
{- -------------------------------------------
(1) コード生成:
「Lbcp の値を更新する (Rj に入っているジャンプ先のオフセット分を足す)」
---------------------------------------- -}
__ add( Lbcp, Rj, Lbcp );
{- -------------------------------------------
(1) コード生成:
「dispatch_next() が生成するコードで,
次のバイトコードに対応するテンプレートへとジャンプする」
---------------------------------------- -}
__ dispatch_next( vtos );
}
This document is available under the GNU GENERAL PUBLIC LICENSE Version 2.