Raspberry Pi Picoの整数除算について (とPico版FreeRTOSの不具合修正)

Raspberry Pi Pico(以下Pico)のCPUであるArm Cortex-M0+には整数除算命令がありませんが、PicoのSoCであるRP2040には、それを補うためにハードウェア除算器が搭載されています。この除算器についての話です。

加えて、以前の記事 [Raspberry Pi PicoでFreeRTOSを動かす](https://qiita.com/yunkya2/items/7b9b38b7c8c33a6327af) で実装したFreeRTOSに存在していた、この除算器に関連する問題を修正します。

# RP2040のハードウェア除算器

Raspberry Pi PicoのCPUであるArm Cortex-M0+には整数除算を行う命令がありません。
x86系CPUでは初代の8086の頃から普通に存在している整数除算命令がないというのは意外に思われるかも知れませんが、ハードウェアで実現しても複数サイクルを要する除算処理というのはRISC CPUには相性が悪いのか、Arm系では伝統的にソフトウェアで処理していて、CPUに整数除算命令が導入されたのは実は割と最近のことだったりします[^1]。

[^1]: Cortex-M系ではCortex-M3から、Cortex-A系はなんとCorex-A15になってようやく導入されています。初期のiPhoneやAndroidスマートフォンではまだ整数除算をソフトウェアでやってたんですね。

PicoのSoC RP2040には、これを補うためにCPUの外にハードウェア除算器が搭載されています。機能の詳細は[RP2040 Datasheet](https://datasheets.raspberrypi.org/rp2040/rp2040-datasheet.pdf)の**2.3.1.5. Integer Divider**で説明されているのですが、レジスタに被除数と除数を書き込むと、結果のレジスタに商と余りが出てくるというシンプルな仕組みになっています。

|オフセット|レジスタ名|説明|
|:--|:--|:--|
|0x60|DIV_UDIVIDEND|符号なし被除数を書く|
|0x64|DIV_UDIVISOR |符号なし除数を書く  |
|0x68|DIV_SDIVIDEND|符号あり被除数を書く|
|0x6c|DIV_SDIVISOR |符号あり除数を書く  |
|0x70|DIV_QUOTIENT |割り算の商が出てくる|
|0x74|DIV_REMAINDER|割り算の余りが出てくる|
|0x78|DIV_CSR      |制御・ステータスレジスタ|
(レジスタはSIOブロックのベースアドレス 0xd0000000 からのオフセットです)

実際にCのソースコードで確認してみます。

```c
#include <stdio.h>
#include "pico/stdlib.h"

int main()
{
    int a, b, q, r;

    stdio_init_all();
    printf("Start divider test\n");

    a = 12345678;
    b = 1234;

    *(int *)0xd0000060 = a;
    *(int *)0xd0000064 = b;

    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");
    __asm__ volatile ("nop");

    r = *(int *)0xd0000074;
    q = *(int *)0xd0000070;

    printf("%u / %u = %u mod %u\n", a, b, q, r);

    while (1)
        ;
}
```

ドキュメントには結果が出てくるまで8サイクルかかるとあるので、レジスタに値を書き込んでから8個のnop(なにもしないアセンブラ命令)を入れています。実行すると想定通りの結果が出ることが分かります。

```
Start divider test
12345678 / 1234 = 10004 mod 742
```


# 高級言語とのインターフェース

さて、普段我々が高級言語でプログラミングを行う際は、CPUに除算命令があるかどうかなど意識することなく割り算を使っていますが、それは実際にはどのように処理されるのでしょうか。

高級言語のコンパイラがソースコードをアセンブリ言語に変換する際、割り算のようなある程度複雑な処理に関してはあらかじめ用意してあるライブラリを呼び出すコードを生成します。
ここでライブラリがどのような機能をどんな名前で提供すべきなのかについて、Arm社がARM EABIという規格として定義していて、具体的には[Run-time ABI for the Arm Architecture](https://developer.arm.com/documentation/ihi0043/latest/)という文書に記載されています。たとえば符号あり整数の除算の場合は、

```c
int __aeabi_idiv(int numerator, int denominator);
```

このような関数を提供すべし、と定められています。
gccでソースコードをコンパイルする際に登場する割り算はこの関数への呼び出しに置き換えられ、その実装はgccに付属するランタイムライブラリであるlibgcc.aで提供されています。

libgcc.aは特定のSoC固有の処理は含まれていないので、割り算については(Pico以外向けの実装でも使われる)ソフトウェア処理が行われるのですが、Pico SDKではこれをハードウェア除算器による割り算で置き換えるため、SDK内に代替ライブラリを用意しています。
https://github.com/raspberrypi/pico-sdk/blob/master/src/rp2_common/pico_divider/divider.S がそのソースコードです。

この代替ライブラリは、SDKを用いたアプリケーションをビルドする際にリンカに渡される`--wrap`オプションによって本来の`__aeabi_idiv()`と置き換えられます。これは、https://github.com/raspberrypi/pico-sdk/blob/master/src/rp2_common/pico_divider/CMakeLists.txt の以下の記述で行われます。

```
    pico_wrap_function(pico_divider_hardware __aeabi_idiv)
``` 

以上の処理によって、通常のCのコードで割り算を行うとRP2040のハードウェア除算器を使うようになるわけです。

# ソフトウェア除算との比較

ではこのハードウェア除算器、ソフトウェアで演算する場合と比べてどの程度速いのでしょうか。
テストアプリを書いて比較してみます。

```divfunc.c
int __real___aeabi_idiv(int, int);

int idiv_hard(int a, int b)
{
    return a / b;
}

int idiv_soft(int a, int b)
{
    return __real___aeabi_idiv(a, b);
}

int idiv_dummy(int a, int b)
{
    return 0;
}
```

与えられた引数で整数除算を行って値を返す関数を定義しました(コンパイラの最適化による影響を防ぐために別ファイルに分けています)。
`idiv_hard()`が通常の割り算で、Pico SDKだと前述のとおりハードウェア除算器が使われます。`idiv_soft()`では`__real___aeabi_idiv()`という関数を呼んでいますが、これはPico SDKによって置き換えられる前の、libgcc.aが持っているソフトウェア処理で除算を行う関数です[^2]。`idiv_dummy()`は計測時の比較用です。

[^2]: 本来の名前は`__aeabi_idiv()`ですが、リンカが`--wrap`オプションによる置き換えを行うと、置き換えられた方の関数名の頭に`__real_`が付くようになっています。

```divtime.c

int64_t measure_div_time(int count, int (*divfunc)(int, int))
{
    absolute_time_t t1, t2;
    int i;

    t1 = get_absolute_time();
    for (i = 0; i < count; i++) {
        divfunc(12345678, 1234);
    }
    t2 = get_absolute_time();
    return absolute_time_diff_us(t1, t2);
}

int main()
{
    uint64_t th, ts, td;

    stdio_init_all();
    printf("Start divider time test\n");

    th = measure_div_time(1000000, idiv_hard);
    ts = measure_div_time(1000000, idiv_soft);
    td = measure_div_time(1000000, idiv_dummy);
    printf("count: hard=%llu soft=%llu\n", th - td, ts - td);

    while (1)
        ;
}
```

先ほどの`divfunc.c`を呼び出して所要時間を計測する処理です。Pico SDKのtimestamp APIを用いて、割り算を100万回行うのにかかる時間をus単位で測って結果を表示します。

実行すると、以下のように表示されます。

```
Start divider time test
count: hard=212771 soft=1008001
```

さすがハードウェア処理、ソフトウェアによる割り算の1/5程度の時間で終了しました[^3]。

[^3]: ソフトウェアで除算を行う場合の所要時間は演算する値によって変化します。この例は12345678/1234を計算した場合の時間で、値によってはこれより速いことも遅いこともあります。

# 割り込み処理対策

除算器のレジスタを直接叩いた例の通り、除算器を使って演算を行う際は

1. 被除数、除数をレジスタに書く
2. 演算終了まで待つ
3. 余りと商をレジスタから読む

このように処理を進めますが、処理の最中に割り込みが発生して、更にその割り込みハンドラの中で別の割り算を行ってしまうと、除算器のレジスタ値を上書きしてしまうため割り込まれたコードで正しい計算結果が得られなくなってしまいます。
これを防ぐため、Pico SDKの割り算処理は実際には、

1. 除算処理中だったら処理完了まで待ってから除算器のレジスタ値を読み出し保存する
2. 被除数、除数をレジスタに書く
3. 演算終了まで待つ
4. 余りと商をレジスタから読む
5. 1.でレジスタを保存していたら元に戻す

このような処理を行うことで、割り込みがあっても安全に割り算が行えるようになっています[^4]。

[^4]: もっとシンプルに、一連の除算処理の間を割り込み禁止にすればそれで十分な気もするのですが何故そうなってないんでしょうね。割り込み禁止区間が長いと割り込み応答性能に悪影響が出ますが、今回のハードウェア除算についてはせいぜい数10クロック程度の処理ですし。

# マルチタスクOS対策

通常のPico SDKの範囲ではシングルタスク動作しかしないので前述の対策で十分ですが、マルチタスクOSを載せて複数のタスクが動作する場合は更に対策が必要です。割り込み処理の場合は最後には割り込まれた処理に戻るのでその場で値を保存・復帰すれば十分ですが、マルチタスクの場合はタスク切り替えによって復帰させた値とは関係のない、まったく別のタスクが動き出す場合もあるからです。

実は、[Raspberry Pi PicoでFreeRTOSを動かす](https://qiita.com/yunkya2/items/7b9b38b7c8c33a6327af) で動作させたFreeRTOSがまさにこの問題に当たってしまっていて[^5]、複数タスクで割り算を行うと結果を誤る可能性があります。

[^5]: というかこの記事で書きたかったのはこの問題についてで、これまでの話は全てその前振りです(笑)。

実際にテストしてこの問題を確認してみます。

```divcheck.c
struct div_task_arg {
    int dividend;
    int divisor;
    int result;
};

void div_task(void *p)
{
    struct div_task_arg *a = (struct div_task_arg *)p;
    int result_check;

    while (true) {
        result_check = a->dividend / a->divisor;
        if (a->result != result_check) {
            vTaskSuspendAll();
            printf("Division failure!!!! expected=%d result=%d\n", a->result, result_check);
            xTaskResumeAll();
        }
    }
}

void timerfunc(TimerHandle_t tm)
{
    taskYIELD();
}

int main()
{
    stdio_init_all();
    printf("Start divider test\n");

    struct div_task_arg arg1 = { 1200, 1 , 1200 / 1 };
    xTaskCreate(div_task, "div_task 1", 256, &arg1, 1, NULL);

    struct div_task_arg arg2 = { 1000, 2 , 1000 / 2 };
    xTaskCreate(div_task, "div_task 2", 256, &arg2, 1, NULL);

    struct div_task_arg arg3 = { 900, 3 , 900 / 3 };
    xTaskCreate(div_task, "div_task 3", 256, &arg3, 1, NULL);

    TimerHandle_t tm;
    tm = xTimerCreate("timer 1", 1, pdTRUE, NULL, timerfunc);
    xTimerStart(tm, 0);

    vTaskStartScheduler();

    while (true)
        ;
}
```

`div_task()`はひたすら割り算を繰り返して事前に与えられた正解と合っているかどうかを確認する関数で、引数の値を変えた3つのタスクでこの関数を実行します。
それとは別に、1ティックごとに起こされるタイマーハンドラ`timerfunc()`からタスク切り替えを行うことで、先ほどの3つのタスクが切り替えながら実行されます。

正常に動いていればもちろんこんな割り算を間違えることはないのですが、実行すると残念ながらこんな感じで演算結果が誤っていることが確認できます。

```
Start divider test
Division failure!!!! expected=300 result=1200
Division failure!!!! expected=1200 result=300
Division failure!!!! expected=1200 result=400
Division failure!!!! expected=300 result=500
Division failure!!!! expected=1200 result=300
   :
```

[Raspberry Pi PicoでFreeRTOSを動かす](https://qiita.com/yunkya2/items/7b9b38b7c8c33a6327af) で最初に行ったFreeRTOS実装では、タスク切り替え時のCPUコンテキスト保存処理にCortex-M0+汎用の処理をそのまま用いていてRP2040固有のハードウェア除算器のレジスタ値を保存していないため、この問題が起きてしまっていました。
これは複数タスクでずっと割り算を続けるというテストなので再現できましたが、通常のプログラムではこんな頻度で割り算は行わないので、たまたま割り算とタスク切り替えのタイミングが重なったときのみ演算結果を誤るという非常に発生頻度の低いバグを残してしまうところでした。

現在のリポジトリ https://github.com/yunkya2/pico-freertos-sample では既にこの問題は修正済みです。[このcommit](https://github.com/yunkya2/pico-freertos-sample/commit/ff51dc3ca3897561a332c473067a502cef9b6f07)で、FreeRTOSのCPUコンテキスト保存処理でRP2040除算器のレジスタ値を保存・復帰させる処理を追加することで修正しています。

上記のテストコードを実行しても、

```
Start divider test
```

このように、エラーが出ずに正常に動作するようになりました。