トップ «前の日記(2007-11-20) 最新 次の日記(2007-11-22)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|02|03|04|05|06|07|08|09|10|11|12|
2023|01|02|03|04|05|06|07|08|09|10|11|12|
2024|01|02|03|

ToDo:


2007-11-21

_ switchの展開

http://alohakun.blog7.fc2.com/blog-entry-878.html

を見てたしかにどういう感じなのかなーと。

たぶん stmt.c の expand_case @gcc-4.2.2 。

最初に unique ならラベルの数とか適当に調べて、 default 以外ターゲットなかったらそこに jump とか。

んで bit なんちゃらがどうこうってのが入ってんだけど、 よくわからんかったからぐぐったら これ面白いな。

http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01733.html

int main(int i) {
    switch (i) {
    case '0':  case '1':  case '2':  case '3':  case '4':
    case '5':  case '6':  case '7':  case '8':  case '9':
    case 'A':  case 'B':  case 'C':  case 'D':  case 'E': case 'F':
        return 1;
    }
    return 0;
}

こんなんを

        subl    $48, %ecx  # とりあえず '0' をひく
        cmpl    $22, %ecx  # 22 よりでかけりゃ ('F'-'0' == 22)
        ja      .L2        # 範囲外なので 0 返すところにゴー
        movl    $1, %eax
        movl    $1, %edx
        sall    %cl, %eax  # 1 << (i - '0') を計算
        testl   $8258559, %eax  # 0b11111100000001111111111 で bitmask
        je      .L2        # ビット立ってなきゃ 0 を返す
        popl    %ecx       # 1 返す
        movl    %edx, %eax
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .p2align 4,,7
.L2:
        popl    %ecx
        xorl    %edx, %edx
        popl    %ebp
        movl    %edx, %eax
        leal    -4(%ecx), %esp
        ret

ほえーすごい。

あとは下記のような条件でテーブルジャンプにならないみたいだ。 case_values_threshold はアーキテクチャ依存で 4 か 5 で、 値の数字の範囲が最適化時は case の数の 10 倍よりデカけりゃ table 化する、って感じか。 あとは細かい話だろう。

      else if (count < case_values_threshold ()
           || compare_tree_int (range,
                    (optimize_size ? 3 : 10) * count) > 0
           /* RANGE may be signed, and really large ranges will show up
          as negative numbers.  */
           || compare_tree_int (range, 0) < 0
#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
           || flag_pic
#endif
           || !flag_jump_tables
           || TREE_CONSTANT (index_expr)
           /* If neither casesi or tablejump is available, we can
          only go this way.  */
           || (!HAVE_casesi && !HAVE_tablejump))

つまり

int main(int i) {
    switch (i) {
    case 0:
        return 1;
    case 1:
        return 9;
    case 2:
        return 6546;
    case 3:
        return 4534;
    case 50:
        return 4324;
    }
    return 0;
}

が限界みたいな感じか。 これだと約 200 Byte くらいのテーブル作るから -Os の時は作られない。 で -Os なら 3 倍が限度なので 15 まで、って感じだな。

なんか読んだ通りの動きしてくれると嬉しいね。

(13:11)

本日のツッコミ(全4件) [ツッコミを入れる]
_ nminoru (2014-05-24 01:42)

swtich 文のジャンプテーブル展開は (1)case ラベルの最小と最大からジャンプテーブルを仮作成 (2)テーブルの充填率を計算して一定以下ならテーブル分割 (3)テーブル群への分岐ツリーを配置、がセオリーだと思っていたのですけど、gcc3/4 はジャンプテーブルの分割ができないんですね。
普通にやっていると信じていたのでショックです。2.97 の頃はできてたような記憶があるんですけど…

_ shinh (2014-05-24 01:42)

GCC-2.97 って RedHat が勝手に名前つけた 2.95 とかでしたっけ…

GCC-2.95.3 のコードざっと見た感じだと table jump の方はあんまり賢いことやってなさそうな気がしますが、コンパイルせずに目視しただけなので正直 GCC のコード読めてる自信はありません…

一応テーブルジャンプにならん時は二分探索になってるように見えますので、やってないのは、分割統治が有効なくらい case が疎でかつテーブルジャンプが有効なほど部分的な case が密、っていう状況があんまり無いと判断した、とかなんですかねぇ。

_ nminoru (2014-05-24 01:42)

2.97 は 2.95 の間違いでした。スイマセン。
さらに i386 の gcc 2.95.3 で確かめてみると、確かにテーブル分割してくれません。

10年くらい前に C コンパイラを書いた時に、この switch 展開コードを(テーブル分割あり)で作ったのですが、その時は``gccを参考''にしながら作った記憶があるのですが…

_ Qojwrjzw (2014-05-24 01:42)

この間も俊太郎の詩をお http://www.stlouisbusinesslist.com/business/5021837.htm?info=viagra buy viagra 8-[

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2007年
11月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
1.phoenix(2014-05-24 01:42) 2.shinh(2014-05-24 01:42) 3.ku-ma-me(2014-05-24 01:42)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h