レジスタ

CPU 内部の最速の記憶場所。

記憶階層での位置#

階層	容量	アクセス
レジスタ	数十個 × 64 bit	1 サイクル未満
L1 キャッシュ	32〜64 KB	約 4 サイクル
L2	数百 KB〜数 MB	約 12 サイクル
L3	数 MB〜数十 MB	約 40 サイクル
主記憶	数 GB〜	200〜300 サイクル

レジスタとメモリでは2 桁以上の差がある。

種類#

種類	用途
汎用レジスタ	演算のオペランド。x86-64 で 16 個、RISC-V で 32 個
プログラムカウンタ	次の命令のアドレス
スタックポインタ	スタックの先端
ステータスレジスタ	演算結果のフラグ（ゼロ、桁上げ、符号）
ベクトルレジスタ	SIMD 用。128〜512 bit

なぜ数が少ないのか#

• 命令の中でレジスタ番号を表すビットが要る。 32 個なら 5 bit、これが命令長を圧迫する
• 物理的に近い場所に置く必要があり、面積の制約がある
• 関数呼び出しのたびに退避・復帰するコストが増える

レジスタ割り当て#

コンパイラの主要な仕事のひとつ。 プログラム中の無数の変数を、有限個のレジスタに割り当てる。

グラフ彩色問題に帰着でき、一般には NP 困難。 実用的には線形走査法などの近似が使われる。

割り当てきれない変数はメモリに追い出される（スピル）。 これが起きると 2 桁遅くなるため、 性能に敏感なコードではレジスタ数が実質的な制約になる。

参考文献#

• David A. Patterson, John L. Hennessy. Computer Organization and Design: RISC-V Edition, 2nd ed. Morgan Kaufmann, 2020.
• Randal E. Bryant, David R. O’Hallaron. Computer Systems: A Programmer’s Perspective, 3rd ed. Pearson, 2016. https://csapp.cs.cmu.edu/
• Gregory J. Chaitin. Register allocation & spilling via graph coloring. SIGPLAN Notices 17(6), 1982. https://doi.org/10.1145/872726.806984