C/C++における整数型の昇格


# いきなり問題です
aとbをcharの変数としたとき、a+bの型は？

## 正解
int

わかった方は以下読まなくてよいです。

# 整数型の昇格とは？
一般的に「型の昇格（type promotion）」とは、小さいサイズの型を持つ値が算術演算（+,-,*,/,%など）時により大きいサイズの型に暗黙的にキャストされることを指す。例えばfloatは算術演算時にdoubleに変換される。
整数型においては、char, signed char, unsigned char, short, unsigned shortは元の情報を失わないならintに、そうでなければunsigned intに変換される。
[C99の仕様](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)では整数型の昇格について以下のような記述となっている
> If an int can represent all values of the original type, the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions

「元の情報を失わない」というのは、16ビット環境ならintとshortは同じサイズになるため、unsigned shortをintに変換しようとすると、0x7fffよりも大きい値はintに入らないことになる。このような場合、unsigned shortはunsigned intに変換されるというわけである。

ちなみにC++だとwchar_tとboolも昇格がある。wchar_tはint,unsigned int, long, unsigned longの優先順で情報を失わない最初の型への変換、boolはintへの変換となる。

# clangではどう解釈しているか？
たとえば以下のようにclangで単純なソースの抽象構文木（AST）を見てみる。ここでは変数の未初期化とか気にしない。OSはUbuntu14.04LTS 64bit版。

```bash
$ cat a.c 
void func(){
  char a,b,c;
  a = b + c;
}
$ clang -Xclang -ast-dump -fsyntax-only a.c 
TranslationUnitDecl 0x35d0410 <<invalid sloc>>
|-TypedefDecl 0x35d0910 <<invalid sloc>> __int128_t '__int128'
|-TypedefDecl 0x35d0970 <<invalid sloc>> __uint128_t 'unsigned __int128'
|-TypedefDecl 0x35d0cc0 <<invalid sloc>> __builtin_va_list '__va_list_tag [1]'
`-FunctionDecl 0x35d0d60 <a.c:1:1, line:4:1> func 'void ()'
  `-CompoundStmt 0x35d10c0 <line:1:12, line:4:1>
    |-DeclStmt 0x35d0f68 <line:2:3, col:13>
    | |-VarDecl 0x35d0e10 <col:3, col:8> a 'char'
    | |-VarDecl 0x35d0e80 <col:3, col:10> b 'char'
    | `-VarDecl 0x35d0ef0 <col:3, col:12> c 'char'
    `-BinaryOperator 0x35d1098 <line:3:3, col:11> 'char' '='
      |-DeclRefExpr 0x35d0f80 <col:3> 'char' lvalue Var 0x35d0e10 'a' 'char'
      `-ImplicitCastExpr 0x35d1080 <col:7, col:11> 'char' <IntegralCast>
        `-BinaryOperator 0x35d1058 <col:7, col:11> 'int' '+'
          |-ImplicitCastExpr 0x35d1010 <col:7> 'int' <IntegralCast>
          | `-ImplicitCastExpr 0x35d0ff8 <col:7> 'char' <LValueToRValue>
          |   `-DeclRefExpr 0x35d0fa8 <col:7> 'char' lvalue Var 0x35d0e80 'b' 'char'
          `-ImplicitCastExpr 0x35d1040 <col:11> 'int' <IntegralCast>
            `-ImplicitCastExpr 0x35d1028 <col:11> 'char' <LValueToRValue>
              `-DeclRefExpr 0x35d0fd0 <col:11> 'char' lvalue Var 0x35d0ef0 'c' 'char'
```

ここで注目してほしいのは、char同士の演算結果をcharに格納するにもかかわらず、IntegralCastによって一度intに変換されて演算され、その結果をcharに戻すことをしていることだ。一方、このソースのcharをlongに変えてみると

```bash
$ cat a.c
void func(){
  long a,b,c;
  a = b + c;
}
$ clang -Xclang -ast-dump -fsyntax-only a.c 
TranslationUnitDecl 0x287d410 <<invalid sloc>>
|-TypedefDecl 0x287d910 <<invalid sloc>> __int128_t '__int128'
|-TypedefDecl 0x287d970 <<invalid sloc>> __uint128_t 'unsigned __int128'
|-TypedefDecl 0x287dcc0 <<invalid sloc>> __builtin_va_list '__va_list_tag [1]'
`-FunctionDecl 0x287dd60 <a.c:1:1, line:4:1> func 'void ()'
  `-CompoundStmt 0x287e078 <line:1:12, line:4:1>
    |-DeclStmt 0x287df68 <line:2:3, col:13>
    | |-VarDecl 0x287de10 <col:3, col:8> a 'long'
    | |-VarDecl 0x287de80 <col:3, col:10> b 'long'
    | `-VarDecl 0x287def0 <col:3, col:12> c 'long'
    `-BinaryOperator 0x287e050 <line:3:3, col:11> 'long' '='
      |-DeclRefExpr 0x287df80 <col:3> 'long' lvalue Var 0x287de10 'a' 'long'
      `-BinaryOperator 0x287e028 <col:7, col:11> 'long' '+'
        |-ImplicitCastExpr 0x287dff8 <col:7> 'long' <LValueToRValue>
        | `-DeclRefExpr 0x287dfa8 <col:7> 'long' lvalue Var 0x287de80 'b' 'long'
        `-ImplicitCastExpr 0x287e010 <col:11> 'long' <LValueToRValue>
          `-DeclRefExpr 0x287dfd0 <col:11> 'long' lvalue Var 0x287def0 'c' 'long'
```

型の昇格はないので、IntegralCastは出てこない。

# 整数型の昇格のあるコードの性能は？
わざわざ無駄にも見えるキャストをしているなら、オーバーヘッドがあって性能が落ちるとかあるのでは？と思い、以下のようなカウンタの変数の型をそれぞれintとshortにして実験を行った。

```bash
$ cat loop.c 
int dummy=0;
void donothing(){dummy++;}
int main(){
#ifdef SHORT_COUNTER
  short i, j;
#else
  int i, j;
#endif
  for(i = 0; i < 0x7fff; i++){
    for(j = 0; j < 0x7fff; j++){
      donothing();
    }
  }
  return 0;
}
$ clang -O0 loop.c 
$ time ./a.out 

real    0m2.862s
user    0m2.861s
sys     0m0.000s
$ time ./a.out 

real    0m2.865s
user    0m2.864s
sys     0m0.000s
$ time ./a.out 

real    0m2.862s
user    0m2.861s
sys     0m0.000s
$ clang -O0 -DSHORT_COUNTER loop.c 
$ time ./a.out 

real    0m4.213s
user    0m4.212s
sys     0m0.000s
$ time ./a.out 

real    0m4.211s
user    0m4.210s
sys     0m0.000s
$ time ./a.out 

real    0m4.209s
user    0m4.208s
sys     0m0.000s
$ clang -O1 loop.c 
$ time ./a.out 

real    0m2.212s
user    0m2.210s
sys     0m0.000s
$ time ./a.out 

real    0m2.216s
user    0m2.215s
sys     0m0.000s
$ time ./a.out 

real    0m2.218s
user    0m2.217s
sys     0m0.000s
$ clang -O1 -DSHORT_COUNTER loop.c 
$ time ./a.out 

real    0m2.208s
user    0m2.208s
sys     0m0.000s
$ time ./a.out 

real    0m2.207s
user    0m2.206s
sys     0m0.000s
$ time ./a.out 

real    0m2.214s
user    0m2.214s
sys     0m0.000s
```

最適化なし（-O0）だと型変換によるオーバーヘッドが顕在化するが、最適化あり（-O1）だとintの場合と差がない。
まあ真面目に実験を評価するなら統計的に有意な回数繰り返して検定とかするんだろうけど、面倒なのでここではそこまではしない。

これはアセンブラレベルで見ると理由が分かる。以下は最適化なしのint版とshort版のアセンブラに対してdiffをとったものである。movwとmovlのようなオペランドのサイズによる命令の差異は性能に影響しないためここでは置いておいて、movswl命令が加わっていることに注目してほしい。movswlは16bitを32bitに拡張するmov命令である。

```diff
--- loop.s.int_O0       2015-02-15 08:17:56.131369812 +0900
+++ loop.s.short_O0     2015-02-15 08:17:43.563369464 +0900
@@ -39,30 +39,32 @@
        .cfi_def_cfa_register %rbp
        subq    $16, %rsp
        movl    $0, -4(%rbp)
-       movl    $0, -8(%rbp)
+       movw    $0, -6(%rbp)
 .LBB1_1:                                # =>This Loop Header: Depth=1
                                         #     Child Loop BB1_3 Depth 2
-       cmpl    $32767, -8(%rbp)        # imm = 0x7FFF
+       movswl  -6(%rbp), %eax
+       cmpl    $32767, %eax            # imm = 0x7FFF
        jge     .LBB1_8
 # BB#2:                                 #   in Loop: Header=BB1_1 Depth=1
-       movl    $0, -12(%rbp)
+       movw    $0, -8(%rbp)
 .LBB1_3:                                #   Parent Loop BB1_1 Depth=1
                                         # =>  This Inner Loop Header: Depth=2
-       cmpl    $32767, -12(%rbp)       # imm = 0x7FFF
+       movswl  -8(%rbp), %eax
+       cmpl    $32767, %eax            # imm = 0x7FFF
        jge     .LBB1_6
 # BB#4:                                 #   in Loop: Header=BB1_3 Depth=2
        callq   donothing
 # BB#5:                                 #   in Loop: Header=BB1_3 Depth=2
-       movl    -12(%rbp), %eax
-       addl    $1, %eax
-       movl    %eax, -12(%rbp)
+       movw    -8(%rbp), %ax
+       addw    $1, %ax
+       movw    %ax, -8(%rbp)
        jmp     .LBB1_3
 .LBB1_6:                                #   in Loop: Header=BB1_1 Depth=1
        jmp     .LBB1_7
 .LBB1_7:                                #   in Loop: Header=BB1_1 Depth=1
-       movl    -8(%rbp), %eax
-       addl    $1, %eax
-       movl    %eax, -8(%rbp)
+       movw    -6(%rbp), %ax
+       addw    $1, %ax
+       movw    %ax, -6(%rbp)
        jmp     .LBB1_1
 .LBB1_8:
        movl    $0, %eax
```

一方、最適化ありの場合はmovswl命令の追加はない。以下はint版とshort版のdiffをとったもの。

```diff
--- loop.s.int_O1       2015-02-15 08:15:40.979366072 +0900
+++ loop.s.short_O1     2015-02-15 08:15:05.271365084 +0900
@@ -36,16 +36,16 @@
 .LBB1_1:                                # %.preheader
                                         # =>This Loop Header: Depth=1
                                         #     Child Loop BB1_2 Depth 2
-       movl    $32767, %ebp            # imm = 0x7FFF
+       movw    $32767, %bp             # imm = 0x7FFF
        .align  16, 0x90
 .LBB1_2:                                #   Parent Loop BB1_1 Depth=1
                                         # =>  This Inner Loop Header: Depth=2
        callq   donothing
-       decl    %ebp
+       decw    %bp
        jne     .LBB1_2
 # BB#3:                                 #   in Loop: Header=BB1_1 Depth=1
        incl    %ebx
-       cmpl    $32767, %ebx            # imm = 0x7FFF
+       cmpw    $32767, %bx             # imm = 0x7FFF
        jne     .LBB1_1
 # BB#4:
        xorl    %eax, %eax
```

つまり、最適化なしだと型の昇格によって命令が増えオーバーヘッドとなるが、最適化すれば~~命令が増えることはなく~~型の昇格によるオーバーヘッドを気にする必要はない。（2019/7/19追記 コンパイラの版数やターゲットに依っては増えるものもある。コメント参照）

# まとめ
* charやshortなどのintより小さい型は算術演算時にintにキャストされる
* 最適化すれば性能が落ちたりすることはないので、Cのコンパイラ作るような人以外は特に気にする必要はない