コンパイラ最適化
コンパイラはプログラム意味論を保ちつつ高速化する。意味保存のため静的解析は保守的近似に頼り、最適化機会を逃しやすい。代表的な最適化を以下に整理する。
ループ変換と並列化
- 依存解析 (dependence analysis): ループの並列化可能性は data dependence で決まる（Allen & Kennedy の FORTRAN→ベクトル形式変換が古典）。Program Dependence Graph (PDG) を作って loop fusion / peeling / unrolling を導く。
- Polyhedral Model: ループ反復空間を整数多面体（affine 不等式の交差）として表し、affine 変換で並列性・局所性を最適化する枠組み。Pluto などが LLVM Pass として実装。Farkas の補題・線形計画と結びつく。
- Optimistic Loop Optimization: 前提条件を実行時検証し、保守的近似を超えてループ変換を可能にする。
ベクトル化
- SLP (Superword Level Parallelism): マルチメディア命令を使い、隣接スカラ演算を束ねてベクトル化。
- 制御フローの divergence analysis と masked vector intrinsics で分岐を含むコードもベクトル化。
- 等式飽和を使うベクトル化: DSP 向け (diospyros) で書き換え規則と e-graph により命令選択を探索。線形代数では SPORES。
SSA とスカラ最適化
- mem2reg（メモリ→SSA レジスタ昇格）、global value numbering (GVN)、lazy code motion など SSA 上の古典最適化。
レジスタ割り付け
- グラフ彩色ベース（干渉グラフを彩色）と、より軽量な Linear Scan Register Allocation（生存区間を線形に走査）。LLVM・Go・各種教育用コンパイラで実装される。
関連
- 実装基盤はllvm-mlir、書き換え探索はequality-saturation・term-rewriting。
- ML系コンパイラの各段はクロージャ変換も参照。
- _moc-prog-lang