ISING REGISTER ALLOCATION～アニーラによるレジスタアロケーション～○熊谷 政仁†，高屋敷 光††東北大学

レジスタアロケーションとは• コンパイル中にソースコード内の変数をCPUのレジスタに割り当てる処理のこと
void solve(int * data){
int n,i,w;for( n=MAX; n>1; n-- ){for( i=0; i<n-1; i++ ){if ( data[i]>data[i+1] ){w=data[i];data[i]=data[i+1];
data[i+1]=w;}
}
}
}

高級言語
FIXSTARS AMPLIFYハッカソン

n = %r1
i = %r2
w = %r3
Etc…

コンパイラ

movl 4(%rdi,%rdx,4), %eax
cmpl %eax, %esi
jle .LBB0_4
movl %eax, (%rdi,%rdx,4)
movl %esi, 4(%rdi,%rdx,4)
jmp .LBB0_4.p2align4, 0x90
.LBB0_7:
movq %r10, %r8
andq $-2, %r8
xorl %eax, %eax
jmp .LBB0_8.p2align
4, 0x90
・・・

レジスタ%r1ト
レジスタ%r2ヲ タシマス….

アセンブリ言語
2021/4/27

2

レジスタアロケーションの難しさ

CPU

速いレジスタキャッシュ
メインメモリ• コードには多数の変数が存在• CPUが実際に持つレジスタの数は少ない
void solve(int * data){
int n,i,w;for( n=MAX; n>1; n-- ){for( i=0; i<n-1; i++ ){if ( data[i]>data[i+1] ){w=data[i];data[i]=data[i+1];
data[i+1]=w;}}}}

変数100個くらい必要
だわ

ディスク

遅い

退避させるからちょっと待ってねコンパイラ

えっ？このCPU
レジスタ10個しかないの？

高級言語• うまくアロケーションしないとレジスタのどれかを一旦メモリに退避(スピル)が必要
2021/4/27→オーバーヘッドが発生• 複数の変数が同時に同じレジスタを使用しないように割り当て

FIXSTARS AMPLIFYハッカソン

3レジスタアロケーションと彩色問題• 古典的にレジスタアロケーションは彩色問題を応用して解くことが出来る
大雑把なコンパイルの流れ

ソース
コード

各変数の生存期間を分析して，変数をノードとする干渉グラフを作成

1

0

2

色付けをもとにレジスタへ割り当て

マシン
コード

3
ノード間にエッジが存在する時は変数が同時に生存しているので，違うレジスタ（色）を与える必要がある

ただし，グラフを色づけることが出来る最小色数を求めるのはNP-hard問題！
2021/4/27
FIXSTARS AMPLIFYハッカソン
そこで最適化問題として量子アニーリング・イジングマシンで解くことを考える

4

QUBO定式化
•2
𝑁−1
𝑁−1
𝑅−1
𝐻 = σ𝑖=0 1 − σ𝑟=0 𝑞𝑖,𝑟 + σ𝑅−1
𝑟=0 σ𝑗∈𝐸[𝑖] 𝑞𝑖,𝑟 𝑞𝑗,𝑟 + σ𝑖=0 σ𝑟∉𝐴[𝑖] 𝑞𝑖,𝑟

• 変数の数：𝑁，レジスタの数：𝑅• 変数𝑖をレジスタ𝒓に割り当てる時：𝑞𝑖,𝑟 = 1，割り当てない時：𝑞𝑖,𝑟 = 0• 𝐸 𝑖 ： 変数 𝑖 と生存期間が重なる変数の集合• 𝐴 𝑖 ： 変数 𝑖 が割り当て可能なレジスタの集合• 制約条件• 各変数をただ1つのレジスタに割り当て（ノードをただ1色で塗る）• 生存期間の重なる変数同士を別のレジスタに割り当て（エッジのあるノード間は別色）• できるだけスピルするレジスタを減らすため• 各変数を割り当て可能なレジスタに割り当て（ノードの色は色付け可能な色から選ぶ）• 変数ごとに型やCPUの構成によって割り当て可能なレジスタが異なるため
FIXSTARS AMPLIFYハッカソン

2021/4/275大規模な彩色問題の分割について• 状況に応じて問題サイズを分割する必要• 変数が多くて量子ビット数を超える場合→ 問題を分割して最適化

12

1

前の分割時に得られた解を含めて次の解を求める．割り当て可能なレジスタを絞る
制約に解のみを与えることにより実現可能
2

3076

FIXSTARS AMPLIFYハッカソン

234
5

103

4

760

5

特定の依存関係だけを取り出して，変数のレジスタ割り当てを決定

476

2021/4/27

56

アプリケーションの構成• Clang/LLVMを利用して中間表現からレジスタ情報を抽出• コードの分析や最適化はLLVMのエコシステムを利用
ソースコード（C++)

Clang/LLVM
中間表現• ベンチマーク （簡単なプログラム）• モンテカルロ法，バブルソート

Amplify (Python)
割り当ての決定バイナリ(X86等)

Clang/LLVM

ここは今後の課題• レジスタはX86_64を想定• 問題は４変数ずつに分割して求解FIXSTARS AMPLIFYハッカソン

2021/4/27

7

for( j=0,Ni=0; j<jmax; j++ ){x=(double)rand()/max;y=(double)rand()/max;
if ( x*x+y*y<=1.0 ) Ni++;}

評価（モンテカルロ法）

pi=(double)Ni/(double)jmax*4;

エッジは各変数(ノード)が重複する生存期間を持つことを示す• 全ての制約を満たした割り当てに成功• 同色のノードは同じレジスタに割り当てられている• エッジがない（生存期間が重ならない）ため，制約を満たせている
FIXSTARS AMPLIFYハッカソン

2021/4/27

8

void solve(int * data){
int n,i,w;for( n=MAX; n>1; n-- ){for( i=0; i<n-1; i++ ){if ( data[i]>data[i+1] ){w=data[i];data[i]=data[i+1];data[i+1]=w;}}}}

評価（バブルソート）
エッジが黒：制約が満たされる
エッジが赤：制約が満たされない• 概ね制約を満たした解を求めることに成功• 同じレジスタに割り当てられるが生存期間の重なる変数が存在• この場合スピルが発生する• 問題の分割方法に改善の余地あり
FIXSTARS AMPLIFYハッカソン

2021/4/27

9

今後の展望• アルゴリズムに関して• スピルコストを考慮したレジスタの選択を行うコスト関数の追加• 解品質を維持したまま問題を分割する手法の考案• 実用性に関して• 量子アニーリング・イジングマシンを用いてレジスタアロケーションを行うLLVM Passの作成• FPGAの高位合成時のリソース割り当てなど他の手法へ応用など• 一般的な大規模なリソース割当の問題に応用• 評価に関して• ほかのレジスタアロケーション手法との実行時間・解品質の比較• その他• いつか論文にしたい(LLVMやコンパイラ最適化など，この辺のドメインに詳しい人がもし居たらご連絡ください)
FIXSTARS AMPLIFYハッカソン

2021/4/27

10まとめ• 新規性• 量子コンピュータを用いたレジスタアロケーション手法の例はまだ無い• 彩色問題を色付け制約付きで定式化した例も無い• 進歩性• 彩色問題によるレジスタアロケーションは品質は良いが柔軟性及び求解コストの側面から不利とされていた•

本手法は様々な制約を当てはめたうえで（たぶん）高速に解を求められる！

• 技術力• 色付け制約付き彩色問題のQUBO定式化• LLVMのバックエンドから中間表現を抽出しベンチマークを作成• Amplifyを用いて手法のProof of conceptを作成• 実用性• 色付け制約により割り付けレジスタの指定，量子ビット数が不足する時の問題分割，色不足の際の問題分割を考慮• 制約違反を起こさず彩色が行えているため，あとはLLVM側に結果を戻せば実際に使用可能
FIXSTARS AMPLIFYハッカソン

2021/4/27

11

以下，予備スライドFIXSTARS AMPLIFYハッカソン

2021/4/27

12

まとめ
• 背景
• レジスタアロケーションについて• 彩色問題によるレジスタアロケーション• QUBOを用いた彩色問題の定式化••••

変数にレジスタが１つだけ割り当てられる制約
生存期間が被る変数に別のレジスタを割り当てる制約

各変数に割り当て可能なレジスタに応じて割り当てる制約問題が大きい場合の分割について• 評価• LLVMから得られた変数情報・レジスタ情報をもとにした色付け評価• モンテカルロ法では正しく割り当てが出来ていた• バブルソートでは制約が破られる場合があった
FIXSTARS AMPLIFYハッカソン

2021/4/27

13

量子ビットによるレジスタ割り当ての表現
4つの変数を4本のレジスタに割り当て4×4個の量子ビットで表現
レジスタ 𝒓01230𝑞0 0

𝑞0 1𝑞0 2𝑞0 31𝑞1 0𝑞1 1𝑞1 2𝑞1 32𝑞2 0

𝑞2 1𝑞2 2𝑞2 33𝑞3 0𝑞3 1𝑞3 2𝑞3 3102

変数
𝑖

3

変数𝑖をレジスタ𝒓に割り当てる時， 𝑞 𝑖 𝑟 = 1
割り当てない時，𝑞 𝑖 𝑟 = 0FIXSTARS AMPLIFYハッカソン

2021/4/27

14

各変数をただ一つのレジスタに割り当てる制約
レジスタ
100
変数

2312෍3𝑟=0𝑞2,𝑟= 𝑞2,0 + 𝑞2,1+ 𝑞2,2 + 𝑞2,3 = 1

0
1

レジスタ4本のうち，1っにしか割り当てられない

2

10003

制約条件： σ𝑅−1
𝑟=0 𝑞𝑖,𝑟 = 1,FIXSTARS AMPLIFYハッカソン

𝑅−1𝑖 ∈ {0, 1, ⋯ , 𝑁 − 1}

𝑅−1
QUBO： 𝐻 = σ𝑁−1
𝑖=0 1 − σ𝑟=0 𝑞𝑖,𝑟2
2021/4/27

15生存期間の重なる変数同士を別のレジスタに割り当てる制約
同じレジスタでは，変数110

各変数が生存期間の重なる変数
𝐸 0 = 1, 3
𝐸 1 = 0, 2, 3
𝐸2 = 1𝐸 3 = 0, 1
23

FIXSTARS AMPLIFYハッカソン

変数1番とは同じレジスタにならない

番と2番の両方が1になることはない

レジスタ
0
変数

123

෍𝑗∈𝐸[2]0𝑞2,0 𝑞𝑗,0= 𝑞2,0 𝑞1,0 = 0

1

1000

20010

3

制約条件： σ𝑗∈𝐸[𝑖] 𝑞𝑖,𝑟 𝑞𝑗,𝑟 = 0, 𝑟 ∈ {0, 1, ⋯ , 𝑅 − 1}
QUBO： 𝐻 = σ𝑅−1
𝑟=0 σ𝑗∈𝐸[𝑖] 𝑞𝑖,𝑟 𝑞𝑗,𝑟2021/4/27

16

各変数が割り当て可能なレジスタに関する制約
102

各変数が割り当て可能なレジスタ番号
𝐴 0 = 0, 1𝐴 1 = 0, 2, 3
𝐴 2 = 0, 3
変𝐴 3 = 1, 2, 3
数

3FIXSTARS AMPLIFYハッカソン

レジスタ4本あるけど，0番と3番にしか割り当てできない𝐴 2 に入ってない1番と2番は0になるようにす
る

レジスタ
0120

300

෍

𝑞𝑖,𝑟𝑟∉𝐴[2]1020

3= 𝑞2,1 + 𝑞2,2 = 000

制約条件： σ𝑟∉𝐴[𝑖] 𝑞𝑖,𝑟 = 0, 𝑖 ∈ {0, 1, ⋯ , 𝑁 − 1}
QUBO： 𝐻 = σ𝑁−1
𝑖=0 σ𝑟∉𝐴[𝑖] 𝑞𝑖,𝑟2021/4/27

17

干渉グラフについて
変数12• 変数0, 1, 3は変数が生存期間が重31

生存期間002

複しているので，同じレジスタに割り当てることは出来ない• 変数2と変数0,3は生存期間が重複
3

FIXSTARS AMPLIFYハッカソン

していないので，同じレジスタでも問題ない

2021/4/2718

評価（モンテカルロ）
LLVMから抽出した，各変数が利用可能なレジスタ番号
0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
2: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
3: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
4: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
5: [1, 2, 9, 10, 11, 12],
6: [31, 32, 33, 34, 35, 36],
7: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
8: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
9: [37, 38, 31, 32, 33, 34, 39, 40, 41, 35, 36, 42, 43, 44, 45]• 全ての変数が，それぞれの利用可能レジスタに正しく割り当て• 割り当てられたレジスタが全て異なるため，オーバーヘッドが発生しない
FIXSTARS AMPLIFYハッカソン

2021/4/27

19

評価（シンプソン）• 変数が多くても制約を守ってレジスタを割り当てられている
FIXSTARS AMPLIFYハッカソンLLVMから抽出した，各変数が利用可能なレジスタ番号
0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
1: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
2: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
3: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
4: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
5: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
6: [31, 32, 33, 34, 35, 36],
7: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
8: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
9: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
10: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
11: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
12: [2, 3, 4, 5, 9, 10],
13: [31, 32, 33, 34, 35, 36],
14: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
15: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
16: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
17: [2, 3, 4, 5, 9, 10],
18: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],2021/4/27
19: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,26, 27, 28,2029, 30]