c# で 2 のべき乗の定数値との演算は最適化されるか?

# 1. 概要

本稿のテーマは、
> c# 言語において、2 のべき乗の整数定数値との乗除算および剰余は、シフト演算あるいはビットマスクに最適化されるか?

です。

これが VC++ や gcc (g++) なら迷いなく YES と答えるんですが、c#では最適化されないという記事を過去にどこかで見かけたような気がします。
なので、今回実験してみることにしました。

# 2. 実験環境

+ OS => Windows 10 (x64)
+ .NET Runtime => .NET 8.0 / .NET 7.0

# 3. 実験方法

最適化されたコードを確認することが目的なのですが、デバッガ無しでコードを追える自信がないので、ちょっと工夫してアセンブリを2つに分けます。

+ アセンブリ1 => 実験対象のコードがあるクラスライブラリ (Release モードで最適化済み)
+ アセンブリ2 => デバッガー上でアセンブリ1 のコードを呼び出すためのコンソールアプリケーション。

アセンブリの作り方や設定、解析の方法については "[(小技) .NET プログラムの手軽?な解析方法](https://qiita.com/rougemeilland/items/c9e720caebe0811349f2)" を参照してください。

肝心のテストコードですが、クラスライブラリ側では以下のようにしました。
```csharp
public static class OptimizeMulAndDiv
{
    private const int _CONSTANT_1024 = 1024;
    private const uint _CONSTANT_UNSIGNED_1024 = 1024;

    public static int MultiplyBy1024(int value) => value * _CONSTANT_1024;
    public static int DivideBy1024(int value) => value / _CONSTANT_1024;
    public static int RemainderAt1024(int value) => value % _CONSTANT_1024;
    public static uint UnsignedMultiplyBy1024(uint value) => value * _CONSTANT_UNSIGNED_1024;
    public static uint UnsignedDivideBy1024(uint value) => value / _CONSTANT_UNSIGNED_1024;
    public static uint UnsignedRemainderAt1024(uint value) => value % _CONSTANT_UNSIGNED_1024;
}
```

呼び出し元のコンソールアプリケーションでは以下のようにしました。
```csharp
var value = 10000;

// 符号付整数の乗算
var mul = OptimizeMulAndDiv.MultiplyBy1024(value); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{value} * 1024 => {mul}");

// 符号付整数の除算
var div = OptimizeMulAndDiv.DivideBy1024(value); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{value} / 1024 => {div}");

// 符号付整数の剰余
var rem = OptimizeMulAndDiv.RemainderAt1024(value); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{value} % 1024 => {rem}");

var unsignedValue = 10000U;

// 符号無し整数の乗算
var umul = OptimizeMulAndDiv.UnsignedMultiplyBy1024(unsignedValue); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{unsignedValue}U * 1024 => {umul}U");

// 符号無し整数の除算
var udiv = OptimizeMulAndDiv.UnsignedDivideBy1024(unsignedValue); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{unsignedValue}U / 1024 => {udiv}U");

// 符号無し整数の剰余
var urem = OptimizeMulAndDiv.UnsignedRemainderAt1024(unsignedValue); // <= ここにブレークポイントを設定して、停止したら逆アセンブリ画面で追跡する。
Console.WriteLine($"{unsignedValue}U % 1024 => {urem}U");
```

# 4. 実験結果

まずはクラスライブラリをデコンパイルしてみました。以下がその結果です。
```csharp
public static class OptimizeMulAndDiv
{
    private const int _CONSTANT_1024 = 1024;

    private const uint _CONSTANT_UNSIGNED_1024 = 1024u;

    public static int MultiplyBy1024(int value)
    {
        return value * 1024;
    }

    public static int DivideBy1024(int value)
    {
        return value / 1024;
    }

    public static int RemainderAt1024(int value)
    {
        return value % 1024;
    }

    public static uint UnsignedMultiplyBy1024(uint value)
    {
        return value * 1024;
    }

    public static uint UnsignedDivideBy1024(uint value)
    {
        return value / 1024;
    }

    public static uint UnsignedRemainderAt1024(uint value)
    {
        return value % 1024;
    }
}
```

うん、見事にソースコードのままですね。少なくとも **IL レベルでは一切の最適化がされていません。**

それでは、機械語レベルではどうでしょうか。上記のソースコードを実行して追跡してみました。
自分の PC が x64 なので、機械語も x64 です。

## 4.1 MultiplyBy1024 メソッド (符号付整数の乗算) の機械語
```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 shl         eax,0Ah        ; 10 ビット論理左シフト
 pop         rbp  
 ret  
```
乗算がシフト命令に最適化されているのがわかります。

## 4.2 DivideBy1024 メソッド (符号付整数の除算) の機械語

```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 sar         eax,1Fh        ; 31 ビット算術右シフト
 and         eax,3FFh       ; 0x000003ff (1023) と AND
 add         eax,dword ptr [rbp+10h]  ; 元の値と加算
 sar         eax,0Ah        ; 10 ビット算術右シフト
 pop         rbp  
 ret 
 ```
乗算と同じく最適化されています。
符号付整数であるためか、ちょっとややこしいコードになっていますが、少なくとも乗除算命令は生成されていません。

## 4.3 RemainderAt1024 メソッド (符号付整数の剰余) の機械語

```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 mov         ecx,dword ptr [rbp+10h]  
 sar         ecx,1Fh        ; 31 ビット算術右シフト
 and         ecx,3FFh       ; 0x000003ff (1023) と AND
 add         ecx,dword ptr [rbp+10h]  ; 元の値と加算
 and         ecx,0FFFFFC00h ; 0x000003ff (1023) をビット反転した値と AND
 sub         eax,ecx        ; 元の値から上記の値を減算
 pop         rbp  
 ret  
```
同じく最適化されています。
一見ややこしいコードですが、前項の除算の機械語と見比べてみると、元の値から "商 * 1024" を引くという意図なのがわかります。
符号付整数だと面倒ですね…

## 4.4 UnsignedMultiplyBy1024 メソッド (符号なし整数の乗算) の機械語

```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 shl         eax,0Ah        ; 10 ビット論理左シフト
 pop         rbp  
 ret  
```
シフト命令に最適化されています。
符号付整数の場合と同じコードです。

## 4.5 UnsignedDivideBy1024 メソッド (符号なし整数の除算) の機械語

```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 shr         eax,0Ah        ; 10 ビット論理右シフト
 pop         rbp  
 ret  
```
同じくシフト命令に最適化されています。
符号付整数と比べると非常に単純です。

## 4.6 UnsignedRemainderAt1024 メソッド (符号なし整数の剰余) の機械語
```
 push        rbp  
 mov         rbp,rsp  
 mov         dword ptr [rbp+10h],ecx  
 mov         eax,dword ptr [rbp+10h]  
 and         eax,3FFh       ; 0x000003ff (1023) と AND
 pop         rbp  
 ret  
```
ビットマスクに最適化されています。
やはり符号付整数と比べて非常に単純です。

# 5. 結論
+ 2 のべき乗の整数定数との乗算/除算/剰余はいずれも **IL レベルでは最適化されない。**
+ しかし、JIT で生成される **機械語では最適化される。** (※ x64 でのみ確認済)
+ 符号付整数の除算と剰余は、最適化はされるものの、符号の処理のせいで単純なビットシフトやビットマスクにはならない。符号付整数の乗算はビットシフトに最適化される。
+ 符号なし整数の乗算・除算・剰余は単純なビットシフトまたはビットマスクに最適化される。

# 6. おまけ

興味のある方は、[今回使用したコードのリポジトリ](https://github.com/rougemeilland/Experiment.CsharpOptimazation) も参照してください。