branch-prediction-and-speculation

分岐予測と投機実行

目的

現代の CPU が分岐をどのように予測し、投機実行を行い、予測を誤った場合にどのように回復するのか、また投機実行がなぜサイドチャネル（Spectre／Meltdown）を生み出したのかを説明し、パフォーマンスチューニングとセキュリティを考慮した低レベルコーディングを結び付けます。

使用する場面

• 分岐の多いホットループのコードが期待どおりの性能を発揮しない場合
• likely／unlikely や分岐のないコードへのリファクタリングを評価する場合
• カーネルの retpoline、IBRS、および同様の緩和策について理解する場合
• シークレットに依存する分岐を含むコードを安全に記述する場合

ワークフロー

1. 分岐予測の基本

Fetch sees conditional branch
├── Predict direction (taken / not-taken)
├── Speculatively execute predicted path
└── On resolve:
    ├── Correct → commit, ~0 penalty (deep pipelines still cost on mispredict)
    └── Wrong → squash, refill from correct PC (10–20+ cycles typical)

パターン：後方分岐はしばしば taken（ループなど）と予測され、前方分岐は not-taken と予測されます。

2. パフォーマンスパターン

/* Predictable — tight loop backward branch */
for (int i = 0; i < n; i++)
    sum += a[i];

/* Unpredictable — data-dependent */
if (data[i] > threshold)  /* hard to predict */
    rare_path();

手法：分岐のない cmov／select、ルックアップテーブル、データのソートによる分岐の削減、ホットパスとコールドパスの分割。

/* Branchless min (integer) */
int m = a < b ? a : b;  /* compiler may lower to cmov */

3. コンパイラヒント（控えめに使用）

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (unlikely(ptr == NULL))
    return -EINVAL;

perf で測定します。現代の予測器にとって、ヒントは魔法ではありません。

4. 投機実行とサイドチャネル

CPU は分岐の結果が判明する前に命令を実行する場合があります。投機されたパスがシークレットに依存するメモリにアクセスすると、キャッシュの状態から情報が漏れる可能性があります（Spectre variant 1）。

緩和策（概要）：

• カーネル：retpoline、IBRS/IBPB、STIBP（カーネルの cpu_show_mitigations を参照）
• コンパイラ：投機的ロードの強化（Clang では -mspeculative-load-hardening）
• コード：定時間暗号。シークレットに依存する分岐やインデックスは使用しません

Meltdown（Intel）：ユーザー空間からカーネルマッピングへのロード。KPTI（ページテーブルの分離）によって修正されています。

5. 測定

perf stat -e branches,branch-misses ./app

branch-misses の比率が高い場合は、ホットな分岐を調査します。

6. エージェントの使用

/branch-prediction-and-speculation Make this comparison function constant-time against Spectre-style leakage

よくある問題

症状	原因	対処法
ループが予想より遅い	終了時の予測ミス	イテレーションを前倒しで処理し、末尾を分岐なしにします
likely が効果を発揮しない	予測器がすでに適切に予測している	まずプロファイリングします
暗号処理でシークレットが漏れる	シークレットのバイト値に基づく分岐	定時間アルゴリズム
緩和策による性能低下	KPTI／retpoline のオーバーヘッド	受け入れるか、シークレットを分離します
「分岐なし」のほうが遅い	CMOV でも両方を実行する	対象の CPU でベンチマークします

関連スキル

• skills/computer-architecture/cpu-pipelines-and-hazards — 制御ハザード
• skills/security/kernel-security — KPTI、CET、投機実行の緩和策
• skills/low-level-programming/cpu-cache-opt — キャッシュタイミングチャネル
• skills/profilers/hardware-counters — branch-misses イベント
• skills/runtimes/binary-hardening — ユーザー空間のハードニングとの重複