概要
https://myhsu.xyz/llvm-machine-scheduler-2/
詳細内容
## LLVMにおけるマシン・スケジューラー - パートII
https://myhsu.xyz/llvm-machine-scheduler-2/
**Original Title**: Machine Scheduler in LLVM - Part II
本記事は、LLVMのマシン・スケジューラーにおける「収益性チェック」フェーズを深く掘り下げ、レジスターとリソースの圧力を管理することで命令スケジューリングを最適化する方法を詳細に解説し、将来的な改善点を提言しています。
**Content Type**: Tools
**Language**: en
**Scores**: Signal:5/5 | Depth:5/5 | Unique:4/5 | Practical:3/5 | Anti-Hype:5/5
**Main Journal**: 84/100 | **Annex Potential**: 86/100 | **Overall**: 88/100
**Topics**: [[LLVM, Machine Scheduler, 命令スケジューリング, レジスター圧力, リソース圧力]]
本記事は、LLVMの命令スケジューリングフレームワークであるMachine Schedulerの第2部として、命令がスケジュールされる際の「収益性チェック」フェーズの深層に迫ります。LLVMは速度と保守性を優先するため、絶対的な最適解ではなく、効率的なヒューリスティックに依存しており、特にレジスター圧力の低減と命令レベル並列性（ILP）の向上を目指しています。
レジスター圧力に関して、著者はそれをプログラムのある時点における同時ライブインターバル数と定義しています。これはレジスター・スピリングの発生可能性を測る指標となり、LLVMはこれを圧力セットと呼ばれるグループで追跡します。個々の命令がレジスター圧力に与える影響は`PressureDiff`というデータ構造で概算され、スケジューリング中に現在の圧力に適用されます。`tryCandidate`関数は、以下の3つの指標を用いてレジスター圧力の影響を評価します。
1. **Excess pressure（過剰圧力）**: しきい値でフィルタリングされ、ノイズとなる小さな圧力変化を除外し、実際に圧力がしきい値を超過する度合いを測定します。
2. **Critical Max pressure（クリティカル最大圧力）**: スケジューリング領域全体の最大レジスター圧力と比較し、新規圧力がそれを超える場合にのみ差分を考慮します。
3. **Current Max pressure（現在の最大圧力）**: スケジュール前の元のプログラムにおける最大レジスター圧力と比較し、新規圧力がそれを超える場合にのみ差分を考慮します。
次に、リソース圧力について、レジスター圧力の概念を個々のプロセッサーリソース（パイプ）に拡張して説明します。目標は、特定のプロセッサーリソースにおける累積的な占有サイクルが、正規化されたクリティカルパス長というしきい値を超えないようにすることです。これは、プロセッサーのリソースユニット数や発行幅を考慮して、占有サイクルを正規化することで実現されます。レイテンシーファクター（発行幅とリソースユニットのLCM）とリソースファクターを用いて、各命令の占有が正規化され、リソースの集中度を評価します。例えば、ユニット数が少ないパイプには高いリソースファクターを割り当てて「ペナルティ」を与え、分散能力が低いことを数値的にモデル化します。
著者は、Machine Schedulerには特にインオーダープロセッサー向けに多くの改善の余地があると指摘しています。過去数十年間、アウトオブオーダープロセッサーが市場を支配し、Machine Schedulerの開発が停滞してきましたが、インオーダープロセッサーではストールやレジスタースピリングが性能に大きな影響を与えるため、スケジューリング品質が極めて重要です。現在のスケジューラーはストールに対して悲観的すぎるため、例えば2サイクルのデータハザードを許容することで10サイクルのレジスタースピリングを排除できるような機会を逃している可能性があります。一時的な解決策として`BufferSize = 1`を使用できますが、これはハザード検出を完全に放棄するため、よりバランスの取れたアプローチが必要です。
さらに、`tryCandidate`における固定された比較順序（レジスター圧力、リソース圧力、レイテンシーなど）も問題です。ある命令がレジスター圧力でわずかに優れていても、リソース圧力で深刻な問題を引き起こす場合、固定順序ではリソース圧力の問題を見落とす可能性があります。著者は、これらの要因それぞれにコストを割り当て、命令候補の集計された（おそらく重み付けされた）コストを比較することで、より包括的な判断が可能になると提案しています。最後に、デバッグメッセージの改善も、この複雑なシステムを理解し開発を進める上で重要であると述べられています。