最新のコンパイラがレジスタに変数をどうやって配置するか徹底解説！
引用元：https://news.ycombinator.com/item?id=43048073
この回答は多分、俺の好きなStack Overflowの回答の一つだな。内容が難しいのにとてもわかりやすいから感心した。＞”グラフ彩色という定番のアプローチは1981年に提案された。”教授が授業でこのトピックを扱ったのが約13年前で、グラフ彩色がレジスタの割り当てにどう関係するかを示したスライドは今でも印象に残ってる。それほどにコンピュータサイエンスの応用としては美しいものだと思う。コード生成はコンパイラ実装の中で意外と難しくて評価されてない部分で、IR最適化パイプラインが終わった後でもいろいろ起こる。レジスタの割り当てもその一つで、これについては専用の本がいくつも書かれるくらいだ。授業の最終プロジェクトはこの理由からレジスタベースのVMをターゲットにしたよ。
この話は’Programming Language Design and Implementation Stack Exchange’にあるんだが、これを指摘するのは間違いを伝えたくてじゃない。Stack Exchangeにはしばしば良い、思慮深い回答が多いと思う。
はい、より理論的なCSの話では確かにそうなんだ。2012年頃からSOはウェブ開発者やコーディングチャレンジをする人で混雑したからね。専門的なSEのネットワークサイトも増加してきたけど、SO自体も色んなタグの基準が大きく違うんだよね。
Stack Exchangeは読むのが好きなものの一つだ。ショートでキレのある回答が多くて、LaTeXもきれいだしさ。特に、Ron Maimonの物理の回答なんて宝の山だよ。
ほとんどのStack Exchangeのウェブサイトはオフラインでも読めるよ、Kiwixが定期的にアーカイブしてるから。
実はこれが俺がChatGPTに書かせることの一つだ。数学のレベルをぴったり合わせたリクエストができるから、時には記号の説明がいらない時もあるしさ。
それに共感。やっぱ文化が全然違うのが面白いね。航空のSEでは素晴らしい回答が見れるのに、SOでは質問や回答の投稿は本当に面倒に感じるようになったから。
残念ながら、理論とは違って実践は難しいことが多いんだ。リニアスキャンやそのバリエーションは、レジスタ割り当てで一般的になってしまった。
GCCは地域ベースのアロケーターを使っていると思う。グラフ彩色を使っていて、どちらかと言うとCallahan/Koblenzの研究に基づいているようだよ。
Chordal graph allocatorsを使って成功しているよ。これらはリラックスの次元をたくさん提供してくれるし、インクリメンタルでピニングもできるのが魅力。気楽に書けば短くて堅牢なコードになるし、ユニットテストにも向いてるよ。
これって本当かな？自分がコンパイラの開発をしていた時（結構前だけど）には、Briggsが最低限だったよ。うちのコンパイラはCallahanの階層レジスタ割り当ての改善版を使ってて、基本的には内側のループでの割り当てを優先する方が、グローバルなグラフ彩色よりも良いって感じかな。内側のループで一度スピリングするのは、直線的な部分で複数のレジスタのスピリングよりもコストが高いから。最適化を気にしない未熟な言語のコンパイラだけがナイーブなRAを使うと思ってるけど。
またJITコンパイラの場合、コンパイル時間が重要な要素だよね。例えばV8は線形スキャンのバリエーションを使ってるし。
少なくともGCCはグラフ彩色アルゴリズムを使っているみたい。LLVMはバージョン3から線形スキャンからカスタムアルゴリズムに移行したらしいけど、今何を使っているのかはわからない。
LLVMは今、”Greedy Register Allocator”って呼ばれるものを使っているようだね。自分の理解では、それは線形アロケータの一種で、いくつかのヒューリスティックを使っているみたい。これについてのプレゼンテーションがあるよ： https://www.youtube.com/watch?v=hf8kD-eAaxg。
コンパイラは理論的コンピュータサイエンスの最も純粋な応用の一つだよね。
自分が学んだパース法の中で、実際のコンパイラでは一般的に使われているものがないってちょっと残念だね。
純粋なコンピュータサイエンスを実際の問題に適用するのは、もちろん自分自身の研究分野だね。
ああ、これはAlexis Kingが書いたんだ。そりゃあこんなに上手く書けるわけだ。
同じ著者による”Parse, don’t validate”も読んだことがあるけど、やっぱりすごく良く書けてると思ったよ。
この記事を読む前に著者を確認しなかったけど、彼女は素晴らしいライターで超才能あるね。
Digital Mars Dコンパイラのレジスタアロケーターについてだが、まず中間コードが基本ブロックとしてつながってて、各ブロックにはローカル変数の数に応じたビットベクターがあるんだ。基本ブロック内で変数が参照されたら、対応するビットがセットされるんだよ。ブロックは深さ優先順にソートされて、変数は使用頻度によって「重み」がつけられるんだ。コード生成時にはレジスタに変数が割り当てられず、使用されるレジスタはビットベクターでマークされる。レジスタの割り当てが終わった後に、まだ使われていないレジスタを「重み」に基づいて変数に割り当てる。これを繰り返すことで余分なレジスタの使用を減らす工夫がされている。 Dの機能の実装についての説明がいつも楽しみだよ！ 俺も書くのが楽しいって感じだ！レジスタアロケーションにAIを使ってる人たちの話を聞いたことあるんだけど、どうなってるんだろうな。俺のコード生成器はわかりにくいって言われるけど、実は超簡単だよ。AArch64にまともに機能させるの大変だったけど、冒険みたいだったね。 こんなに高品質な回答が多項式時間最適レジスタアロケーションアルゴリズムについて触れてないのが意外だわ。グラフ彩色はNP完全だけど、その制約を外すことでポリノミアル時間の解法が存在するらしい。実際に使われてるらしいけど、詳細はよく知らない。 どこか良い参考文献はあるかな？ 何を勧めればいいかわからないよ。Google Scholarをちょっと探ってみたら、ポリノミアル時間の最適レジスタアロケーションや、Chordal干渉グラフについての有望そうなサーベイがたくさんあったけど、どれを勧めればいいかの決め手がないんだ。Pereiraの2008年の論文がその大発見に近いと思ってるし、詳しくはここに載ってるリンクがあるよ。最適なポリノミアル時間レジスタ割り当てアルゴリズムがクローズアップされているんだ。17年も経って、最近の進展が気になるところだ。 なんでコンパイラがキャッシュを管理しないのかを詳しく解説できる人いる？レジスタアロケーションは一番効率良く操作できるキャッシュの最低限の部分って思うんだけど、上位レベルではハードウェア頼りになっちゃってるのか。 一応、キャッシュを明示的に管理することは可能だよ。再利用しないものをメモリから直接読み込んだり、先読みしたり、キャッシュからラインを取り除くこともできる。高パフォーマンスコードでは有用なんだ。ただ、実際やってみると難しいことも多くて、たとえばLinuxカーネルではbranch speculationの問題があって、どんなに注意しても最適化が失敗することもあったんだ。これをコンパイラに任せるとなると、プログラムの実行からのプロファイリング情報が必要になってくる。 Javaのパフォーマンスが思った以上に良い理由は、JVMやガーベジコレクションのオーバーヘッドを考慮しても無料でプロファイルが得られて、それが多くの問題をカバーするからなんだ。レイテンシを重視する企業がJVMを使う理由の一つだね。 ＞そのアイデアを真剣に考えて、様々なエンジニアが注意深く埋め込んだヒントはしばしばひどい結果になったこともあるから、結局それを取り除くことでカーネルのパフォーマンスが上がったんだ。 レジスタ割り当ては値解析の一種だけど、キャッシュ管理はポインタ解析の一種で、100倍難しいんだ。エイリアシングの問題があって、X[i]とY[j]が別々のメモリ位置か判断するのが難しいから、コンパイラはX[i]がY[j]を上書きするかもって慎重になる必要がある。C99の’restrict’キーワードや言語の新しいセマンティクスには改善点もあるけど、エイリアシングを完全には排除できない。つまり、最新のコンパイラは99.9％の開発者よりレジスタ割り当てで優れてるけど、キャッシュメモリを明示的に管理する開発者には勝てないってわけだ。 GameBoy AdvanceはキャッシュがないCPUだったけど、チップに32kbitの速いRAMがあった。完全に手動のキャッシュに近かったけど、実際には完全に無駄だったんだ。貸し出したり再利用するのが現実的ではなかったから、ソフトウェアでメモリアロケーターやハッシュテーブルを作る必要があった。管理は面倒で負担にもなったよ。ほとんどのゲームはこのRAMを利用せず、アッセンブリでループをコピーするだけだったから。 レジスタはx86_64で固定されてるけど、キャッシュはCPUハードウェア特有なものだよね。新しいCPUは古いものよりキャッシュが多いけど、レジスタの数はx86で8、x86_64で16に固定されてる。そのため、コンパイラはコンパイル時にレジスタで作業できるけど、キャッシュの構造は未知数なんだ。 キャッシュの使い方はコンパイル時に静的にはわからないよ。データベースからアイテムを取得すれば、別のアイテムを取得したときとは異なるキャッシュの使用が発生する。 他の良い答えに加えて、ソフトウェアが明示的に管理する状態が大きくなりすぎると、その状態を保存したり復元するのが高くつくんだ。例えば、システムコールでOSに制御が移るときにそうなる。もしキャッシュがソフトウェア管理だったら、OSはメインメモリに全てフラッシュするか、位置をそのままにしてOSのコードやデータをキャッシュしないか決める必要があるんだ。 キャッシュはプログラムに透明に設計されてて、ハードウェアメーカーが追加してベンチマークを改善するために再コンパイルなしでずっとそのままなんだ。それ以降、ハードウェアメーカーがISAを変更することなく改良するのが楽だから、この状態が続いているよ。 I$プレッシャーって、高ボリューム情報でマシンコードが膨らむことだよね。プリフェッチやclflush命令、非テンポラルストアや書き込み結合ストアの概念を参照しつつ。具体的にはそういうこと。 レジスタ割り当てをもっと体系的にプログラマが制御できる’ハイレベルな構造化アセンブリ言語’を見てみたいね。‘オプティマイザがもっと良い仕事をする’って言うかもしれないけど、そういうのが機械コードになるのではなく、もっと単純でローカルな変換で変えられる言語があったらいいなと思う。つまり、高レベルのシステム言語に最適化バックエンドの依存が増えて、‘ポータブルアセンブリ’から離れていく中で、Cよりも下でアセンブリよりも上の概念空間が広がる気がするんだ。 Jasminっていうのがそれに近いもので、基本的にはハイレベルアセンブラで、レジスタ割り当てを扱ってくれる（ただしスピルはなし）。基本的な制御フロープリミティブもあって、アセンブリ命令に直接マッピングされる。形式的検証コンポーネントもオプションであって、ある関数がその参照と同等で、サイドチャネルフリーであることを証明できるよ。 ありがとう、これすごく面白いね。 マクロアセンブラが欲しいってことなんじゃないかな。ハードウェアに近すぎると思うかもしれないけど、レジスタの割り当てをちゃんと制御したいなら、特定のCPU用のコードを書くことになるからね。C言語って本当にポータブルなアセンブリだったことあったっけ？最初はコンパイラが生成するアセンブリが予測できたけど、ポータブルになったら最適化が求められるようになって、コードの予測は難しくなったよ。 “最適化がもっと上手くなる”って言うかもしれないけど、その通りだよ。それが、このジャンルで良いものがまだ作られていない理由なんじゃないかな。ほんとに真剣なプロジェクトはコンパイラの最適化を選ぶだろうね。 問題は、最適化が積極的に妨害される必要がある分野がいくつかあることだよ。低レベルな暗号化のプリミティブなんかは特にそう。Cで書くと信頼性がないから、アセンブリに落ちて最適化を妨害しないといけないけど、アセンブリが理想的な選択ってわけじゃない。 その通りだと思う。最適化がほぼ完璧に機能することを願うのは素敵だけど、時にはそれが実現しないこともあるんだ。例えば、AMDのGPU ISA（GCN）を生成するLLVMなんて、最適からほど遠い状態が長すぎて、いつ改善されるのか希望が持てないよ。 amdgcnのGCCバックエンドはマシなのか？もしくは、最終的なレジスタ割り当てはllvm-mcが呼ばれる前に行われないのかな？GCCはbinutilsがサポートされていないせいでllvm-mcを再利用してるらしいけど。 Forthっぽいね。 与えられた例の関数がx86上で一命令に簡略化できる計算をしているのが面白いな。eaxの中に入力xと戻り値があれば、”lea eax, [eax+eax*4+7]”で済むから。コンパイラはレジスタ割り当ての前にこういう簡略化をする可能性が高いと思うんだよ。 間違ってはいないよ、全ての最適化は互いに依存している。だけど、理由はいろいろあるけど、最適に全てを一度に行うのは難しいんだ。一般的に“レジスタプレッシャーを考慮した”選択やスケジューリングを行ったりしているよ。 “最適化結果がサブオプティマルに終わる場合が多い”ってのは間違ってるわけじゃない。でも、そうしないと大きな欠点がある：全てのレジスタ割り当て決定は厳格にローカルなものにしないといけないから、他の命令や制約についての情報が手に入らないんだ。そんな感じで、私達が使ってるコンパイラではISel+RegAlloc（+Encoding）を一度で組み合わせて実行してるから、余計な移動命令やスピルが多く発生してるよ。 それって“遅いlea”のケースの一つじゃない？（リンク先あり）EBP/RBP/R13を使わなきゃいけないかどうかは分からないけど、遅くなる理由を探るのは難しいな。 rbpやr13がいるのはx86のModR/Mのエンコーディングに面白い理由があるんだよね。例えば、[rbp + rax8]は必ず[rbp + rax8 + 0]として扱われるから、3オペランドのleaみたいに動くんだ。まぁ、[rbp]の件は関係ないけどね。 面白いことに、clangはそういう下げ方しないんだ。代わりに別のステップで7を掛ける。一方でGCCはそうする。 clangに渡すフラグによって異なるんだよ。理由はちゃんとあって、3項leaは”複雑なデコーディング”を使うから、先代のintelアーキテクチャではレイテンシーが高いんだ。だから、-O2 -mtune=icelake-clientや- mtune=znver3をつければ単一のlea命令にできるんだ。最終的にはコストモデリングとトレードオフの話だよ。 面白いね。GCCのコストモデリングが違うのかな？それともデフォルトで新しい機械を使ってる？ コンパイラは定数でシフトアンドアドを出力すると思う。leaよりも早いことが多いかも。 そうだけど、x86ってほんと変わってるよね:Ｄ 多分初心者の理解だけど、すべてのCPU操作はレジスタで行われるから、変数は操作されるときにレジスタに移動する必要があるんだ。だから、”どの変数が”の質問には”すべて”が答えになってしまう。つまり、その質問は、しばらく使われていない変数をレジスタに保持するものについてかな？ 基本的にはキャッシュの問題だよ。変数をアンロードして新しい変数を読み込むのには時間がかかるから、その時間を最小化したい。コンパイラはコードを読めるから、使われる変数の数やタイミングを正確に知ってる。だから、ルールなしのキャッシュよりも効果的にレジスタの配置を最適化できるんだ。 ＞”CPUの観点からは、そうだけど、多くの命令セットアーキテクチャ（特に非常に一般的なx86ファミリー）には、オペランドがレジスタかメモリロケーションのいずれかになり得る命令がある。”ここで言うメモリロケーションはCPUが内部レジスタに読み込んでから操作する形式だけど、コンパイラの観点ではCPUはメモリを直接操作していると言えるね。＞”一部の操作はレジスタを介さずにメモリで行うことができるの？”一部のアトミックメモリアクションはメモリで直接やってるかもしれない。 ターゲットCPU次第だけど、一部のCPUはRAM上で直接動作する命令があるんだ。ただ、RAMはレジスタに書き込むよりもほぼ常に2～4倍遅いから、通常はRAMからレジスタにコピーするのが効率的なんだ。大抵のCPUはレジスタで動作するように設計されてるけど、RAMの変数を中間コピーなしで増やすとかは普通にある。 完璧ではないけど、問題を理解するには十分な直感を与えてくれるね。 全てのCPUの演算はレジスタだけで行われるわけじゃないよ。例えば’INC EA’みたいな命令があるし。 1975年の6502でも同じような命令があるからね。 レジスタとx87スタックの使い方には、それぞれに最適でないケースがあるんだよね。参考にしてみて。 一番投票が多い回答を読んでたら、Jon Hannibal Stokesの初期のCPUプラクティスを思い出したよ。誰かこのことを覚えてる人いる？もっとコメントを表示（1）
こういうことがあったのか、プロファイルをうまくとらないと最適化がうまくいかない経験をしたから、同じように感じるよ。もっとコメントを表示（2）
もっとコメントを表示（3）
