# 機能設計書 10-Polly

## 概要

本ドキュメントは、Polly（多面体最適化フレームワーク）の機能設計を記述する。PollyはLLVMプロジェクトの多面体最適化フレームワークであり、ループ最適化やデータローカリティ最適化を自動的に行う。

### 本機能の処理概要

Pollyは、LLVM IRを入力として、静的制御部分（SCoP: Static Control Part）を検出し、多面体モデルを用いた高度なループ最適化を適用する。ループ並列化、タイリング、ベクトル化などの最適化を自動的に実行する。

**業務上の目的・背景**：科学計算や数値計算プログラムの自動最適化を提供する。多面体コンパイラ技術を活用して、キャッシュ局所性の向上、並列化、SIMD活用などの高度な最適化を行う。研究用途と実用途の両方に対応する。

**機能の利用シーン**：
- 数値計算コードの自動最適化
- ループ並列化の自動適用
- GPUオフロードコードの生成
- キャッシュ効率の最適化
- コンパイラ研究・教育

**主要な処理内容**：
1. SCoP（静的制御部分）検出
2. 多面体モデルへの変換
3. スケジューリング最適化
4. コード生成
5. ベクトル化準備

**関連システム・外部連携**：
- LLVM Coreとの連携
- isl（Integer Set Library）ライブラリ
- Clangコンパイラ

**権限による制御**：特になし（LLVMパスとして実行）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | PollyはLLVMパスプラグインであり、GUI画面は持たない |

## 機能種別

最適化パス / ループ最適化 / 多面体コンパイラ

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| -polly | flag | No | Polly有効化 | true/false |
| -polly-vectorizer | string | No | ベクトル化戦略 | none/stripmine |
| -polly-parallel | flag | No | 並列化有効 | true/false |
| -polly-optimizer | string | No | スケジューラ選択 | none/isl |
| -polly-position | string | No | パス位置 | early/before-vectorizer |
| -polly-show | flag | No | SCoP可視化 | true/false |
| -polly-export | flag | No | JScop出力 | true/false |
| -polly-import | flag | No | JScop入力 | true/false |

### 入力データソース

- LLVM IR（ビットコード/アセンブリ）
- JScop形式のスケジュール定義

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 最適化済みIR | .bc/.ll | 最適化後のLLVM IR |
| JScop出力 | .jscop | 多面体表現 |
| DOT出力 | .dot | SCoP可視化 |
| 診断メッセージ | text | 最適化レマーク |

### 出力先

- ファイル（-oオプションで指定）
- 標準エラー（最適化レマーク）

## 処理フロー

### 処理シーケンス

```
1. パス登録
   └─ LLVMパスとして登録（プラグイン）
2. SCoP検出
   └─ 静的制御フロー領域の識別
3. 多面体モデル構築
   └─ ScopInfo生成
4. 依存性解析
   └─ データ依存関係の分析
5. スケジューリング
   └─ islによる最適化スケジュール計算
6. コード生成
   └─ 最適化後IRの生成
7. クリーンアップ
   └─ 後処理パス適用
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[パス登録]
    B --> C[SCoP検出]
    C --> D{SCoP発見?}
    D -->|No| E[スキップ]
    D -->|Yes| F[ScopInfo構築]
    F --> G[依存性解析]
    G --> H{最適化有益?}
    H -->|No| I[Unprofitable判定]
    H -->|Yes| J[スケジューリング]
    I --> E
    J --> K[ISL最適化]
    K --> L[AST生成]
    L --> M[コード生成]
    M --> N[クリーンアップ]
    N --> O[終了]
    E --> O
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-001 | パス位置選択 | early または before-vectorizer | -polly-position |
| BR-002 | ISLデフォルト | ISLスケジューラがデフォルト | オプティマイザ未指定時 |
| BR-003 | Unprofitable除外 | 利益のないSCoPは除外 | 解析結果 |
| BR-004 | AST生成必須 | コード生成前にAST生成 | 最適化実行時 |

### 計算ロジック

- SCoP検出：制御フロー解析とアフィン制約検出
- 依存性解析：多面体依存性グラフ構築
- スケジューリング：ISLによる最適化スケジュール計算

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | Pollyはデータベースを使用しない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------
| - | SCoP検出失敗 | アフィン制約不成立 | コードを単純化 |
| - | ISLエラー | 複雑すぎるSCoP | サイズ制限 |
| - | コード生成失敗 | 非サポートパターン | 手動最適化 |

### リトライ仕様

リトライは行わない。問題発生時はSCoP除外で継続。

## トランザクション仕様

Pollyはデータベーストランザクションを使用しない。

## パフォーマンス要件

- 大規模ループネストの効率的な解析
- ISL計算のタイムアウト制御
- メモリ使用量の制限

## セキュリティ考慮事項

- 入力IRの検証
- ISL計算リソースの制限

## 備考

Pollyは研究用途のみならず、プロダクションコンパイラとしても使用可能である。ISLライブラリとの緊密な連携により、最先端の多面体最適化技術を適用できる。

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: プラグインエントリーを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Polly.cpp | `polly/lib/Plugin/Polly.cpp` | プラグインエントリー |

**主要処理フロー**:
1. **17-20行目**: llvmGetPassPluginInfo関数 - プラグインエントリー
2. **19行目**: getPollyPluginInfo()呼び出し

#### Step 2: パス登録を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | RegisterPasses.cpp | `polly/lib/Support/RegisterPasses.cpp` | パス登録処理 |

**主要処理フロー**:
- **66-73行目**: PollyCategory定義（コマンドラインオプションカテゴリ）
- **70-73行目**: -polly オプション定義
- **625-676行目**: registerPollyPasses関数 - パス登録メイン
- **648-665行目**: パイプラインパースコールバック登録
- **667-674行目**: パス位置によるコールバック登録
- **678-681行目**: getPollyPluginInfo関数

#### Step 3: SCoP解析を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | ScopInfo.cpp | `polly/lib/Analysis/ScopInfo.cpp` | SCoP情報構築 |

**主要処理フロー**:
- **8-16行目**: ScopInfoの目的説明（多面体記述生成）
- **76-113行目**: 各種統計情報定義
- **89行目**: NumScops統計（検出SCoP数）

### プログラム呼び出し階層図

```
llvmGetPassPluginInfo (Polly.cpp:17)
    │
    └─ getPollyPluginInfo (RegisterPasses.cpp:678)
           │
           └─ registerPollyPasses (RegisterPasses.cpp:625)
                  │
                  ├─ パイプラインパースコールバック登録
                  │      ├─ parseFunctionPipeline
                  │      ├─ parseCGPipeline
                  │      └─ parseModulePipeline
                  │
                  └─ パス位置コールバック
                         ├─ [POSITION_EARLY]
                         │      └─ buildEarlyPollyPipeline (RegisterPasses.cpp:477)
                         │
                         └─ [POSITION_BEFORE_VECTORIZER]
                                └─ buildLatePollyPipeline (RegisterPasses.cpp:506)

パス実行フロー:
buildCommonPollyPipeline (RegisterPasses.cpp:460)
    │
    └─ PollyFunctionPass(Opts)
           │
           ├─ ScopDetection (検出)
           ├─ ScopInfo (構築)
           ├─ DependenceInfo (依存解析)
           ├─ ScheduleOptimizer (スケジューリング)
           ├─ IslAst (AST生成)
           └─ CodeGeneration (コード生成)
```

### データフロー図

```
LLVM IR入力
        │
        v
+------------------+
| registerPollyPasses |
+------------------+
        │
        v
+------------------+
| ScopDetection    |
| (SCoP検出)       |
+------------------+
        │
        v
+------------------+
| ScopInfo         |
| (多面体モデル構築)|
+------------------+
        │
        v
+------------------+
| DependenceInfo   |
| (依存性解析)     |
+------------------+
        │
        v
+------------------+
| ScheduleOptimizer|
| (ISL最適化)      |
+------------------+
        │
        v
+------------------+
| IslAst           |
| (AST生成)        |
+------------------+
        │
        v
+------------------+
| CodeGeneration   |
| (コード生成)     |
+------------------+
        │
        v
最適化済みLLVM IR
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| Polly.cpp | `polly/lib/Plugin/Polly.cpp` | ソース | プラグインエントリー |
| RegisterPasses.cpp | `polly/lib/Support/RegisterPasses.cpp` | ソース | パス登録 |
| ScopInfo.cpp | `polly/lib/Analysis/ScopInfo.cpp` | ソース | SCoP情報 |
| ScopDetection.cpp | `polly/lib/Analysis/ScopDetection.cpp` | ソース | SCoP検出 |
| DependenceInfo.cpp | `polly/lib/Analysis/DependenceInfo.cpp` | ソース | 依存解析 |
| ScheduleOptimizer.cpp | `polly/lib/Transform/ScheduleOptimizer.cpp` | ソース | スケジューリング |
| IslAst.cpp | `polly/lib/CodeGen/IslAst.cpp` | ソース | AST生成 |
| CodeGeneration.cpp | `polly/lib/CodeGen/CodeGeneration.cpp` | ソース | コード生成 |
| RegisterPasses.h | `polly/include/polly/RegisterPasses.h` | ヘッダ | パス登録API |
| ScopInfo.h | `polly/include/polly/ScopInfo.h` | ヘッダ | SCoP情報API |
