**コンパイラ最適化に関する二つの研究**

目次

• はじめに
• ケース 1：モジュラー増分
  • シナリオ
  • ペイホール最適化
  • ループ不変量
  • すべての道筋
• ケース 2：エンディアン変換
  • シナリオ
  • 命令選択
  • コンパイラを助ける
  • 並び替え、再検討
  • 自分自身に足を踏み入れる
• 結論
• 補遺：その他の資料

---

はじめに

多くの性能志向プログラマは、現代コンパイラがコードを最適化するというほぼ超自然的な能力に精通していますが、その魔法がどのように実行されているかを内部まで調べることはほとんどありません。彼らの質の証として、私たちは単にコンパイラをブラックボックスとして扱います：可読コードが入力され、速いバイナリが出力されます。しかし、一見無害な変更―たとえコンパイラを助けることを意図しているものでも―は、背後にある機構を深く理解しないと説明しづらい驚くべき性能問題を引き起こす可能性があります。

本稿では、2 つのシンプルな例を用いて LLVM の最適化パスがどのように実装されているかを掘り下げます。小さなソース変更がコンパイラ内部で異なる経路をトリガーし、予期せぬ結果をもたらす様子を示します。高性能を達成することは、コンパイラ開発者とユーザーの両方にとって芸術と科学の両面があります。いくつかの演習が含まれていますが、フォローするために必須ではありません。

本稿全体で使用しているバージョンは LLVM 22.1.0 です。例は（非常に基本的な）C++23 で書かれており、ターゲットは x86‑64、アセンブリは Intel 構文を採用しています。LLVM IR の事前知識は必須ではありませんが、役立つ場合があります（A Gentle Introduction to LLVM IR を参照）。

---

ケース 1：モジュラー増分

シナリオ

配列またはベクターにラウンドロビン方式でアクセスする次のインデックスを返す関数を考えてみましょう。

unsigned next_naive(unsigned cur, unsigned count)
{
    return (cur + 1) % count;
}

このコードは、32 ビット除算命令が必要になるため、

count

が実行時に動的な値である限りコンパイラはより安価な演算に置き換えることができません。

しかし

cur

は常に

count

より小さいと分かっています。この事実を利用して除算を条件付きムーブに置き換えることができます。

unsigned next_cmov(unsigned cur, unsigned count)
{
    auto n = cur + 1;
    return n == count ? 0 : n;
}

同じ結果は、C++23 の新しい

[[assume]]

属性を使っても得られます。

unsigned next_assume(unsigned cur, unsigned count)
{
    [[assume(cur < count)]];
    return (cur + 1) % count;
}

ペイホール最適化

この最適化がどこから来るのかを確認するために、InstCombine の前後で LLVM IR を調べます。

urem

命令から

icmp

＋

select

ペアへの変換は InstCombine で行われます。

%cmp = icmp ult i32 %cur, %count
call void @llvm.assume(i1 %cmp)
%add = add i32 %cur, 1
-  %rem = urem i32 %add, %count
+  %0   = icmp eq i32 %add, %count
+  %rem = select i1 %0, i32 0, i32 %add
ret i32 %rem

InstCombine は制御フローグラフを変更しない多くのペイホール最適化に責任があります。関数内のすべての命令を訪問し、何百ものパターンと照合します。関連するパターンは

InstCombineMulDivRem.cpp

にあります。

if (match(Op0, m_Add(m_Value(X), m_One()))) {
    Value *Val = simplifyICmpInst(ICmpInst::ICMP_ULT, X, Op1,
                                 SQ.getWithInstruction(&I));
    if (Val && match(Val, m_One())) {
        Value *FrozenOp0 = Op0;
        if (!isGuaranteedNotToBeUndef(Op0))
            FrozenOp0 = Builder.CreateFreeze(Op0,
                     Op0->getName() + ".frozen");
        Value *Cmp = Builder.CreateICmpEQ(FrozenOp0, Op1);
        return createSelectInstWithUnknownProfile(
                Cmp, ConstantInt::getNullValue(Ty), FrozenOp0);
    }
}

コンパイラは

icmp

結果を折りたたむために使用される同じ分析（

simplifyICmpInst

）と、そのヘルパー

simplifyICmpWithDominatingAssume

を再利用します。後者は

llvm.assume()

への呼び出しで示された仮定を確認し、私たちの条件を暗黙的に意味するかどうかを判定します。

アサーションが有効になっている場合も同様の最適化が行われます。

unsigned next_assert(unsigned cur, unsigned count)
{
    assert(cur < count);
    return (cur + 1) % count;
}

分析は

assert()

マクロに埋め込まれた条件を

isImpliedByDomCondition()

を介して使用します。

---

演習 1

分岐なしでブランチを避けるビット演算を使って関数を書き換えてください。

unsigned next_bitwise(unsigned cur, unsigned count)
{
    auto n = cur + 1;
    return n & -(n != count);
}

InstCombine は

next_cmov()

と同じ出力を生成します。

sub

から始まるビジターのシーケンスを追跡し、どのパターンがマッチするか確認してください。

---

ループ不変量

最適化には

cur

と

count

の関係を明示的に指定する必要があります。別のケースでは、この関係は暗黙であることもあります。例えば、モジュロ値をループ内で反復処理するときです。

void iterate_1(unsigned upto, unsigned count)
{
    for (unsigned i = 0, r = 0; i < upto; ++i, r = (r + 1) % count)
        asm("" :: "r"(r));
}

生成されたアセンブリは、コンパイラがモジュロを最適化しなかったことを示しています。

iterate_1(unsigned int, unsigned int):
    test edi, edi
    je .LBB4_3
    xor edx, edx
.LBB4_2:
    inc edx
    mov eax, edx
    xor edx, edx
    div esi
    dec edi
    jne .LBB4_2
.LBB4_3:
    ret

InstCombine の

visitURem()

は、

X

が PHI ノードであってもパターンをマッチします。

%r.0 = phi i32 [ 0, %entry ], [ %rem, %for.body ]

簡略化は失敗します。これは

0 < count

を判断できないためです。

count == 0

の早期リターンを追加するとギャップが埋まり、期待通りの結果になります。

コンパイラはまた、PHI ノードの第2入力である

r < count

を扱うより深いパターンも処理します。

// icmp pred (urem X, Y), Y
if (match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
    switch (Pred) {
        case ICmpInst::ICMP_NE:
        case ICmpInst::ICMP_ULT:
        case ICmpInst::ICMP_ULE:
            return getTrue(ITy);
    }
}

---

演習 2

ループ条件を

i < std::min(upto, count)

に変更し、コンパイラがもう

urem

命令を書き換えられないようにしてください。

isImpliedByDomCondition()

から始めて、

std::min/std::max

の慣用句を評価条件に組み込む場所を特定し、既存の分析コードを再利用できるかどうか確認してください。

---

すべての道筋

補助変数を削除してループカウンタから直接剰余を計算できます。

void iterate_2(unsigned upto, unsigned count)
{
    for (unsigned i = 0; i < upto; ++i)
        asm("" :: "r"(i % count));
}

生成コードはまだ条件付きムーブを使用しますが、

i

をインクリメントし

count

と比較するだけです。

iterate_2(unsigned int, unsigned int):
    test edi, edi
    je .LBB5_3
    xor eax, eax
    xor ecx, ecx
    xor edx, edx
.LBB5_2:
    inc ecx
    cmp ecx, esi
    cmove ecx, eax
    inc edx
    cmp edi, edx
    jne .LBB5_2
.LBB5_3:
    ret

この変換は InstCombine ではなく、指示選択直前に実行される

CodeGenPrepare

パスから来ます。これはループ強度削減（LSR）後に走りますが、

i

が本体内で剰余を計算するためダウンカウンタに置き換えることはできません。

CodeGenPrepare

は特定のパターンを検出し、ほぼ最適なコードへ変換します。

---

演習 3

iterate_2()

を iterate.cpp に保存して次を実行してください。

clang++ -O2 -S -emit-llvm -fno-discard-value-names -o- iterate.cpp |
opt -S -passes="require<profile-summary>,loop-reduce,codegenprepare" -

最後にもう一度

loop-reduce

パスを追加すると何が起こるか確認してください。

---

演習 4

演習 2 で行ったように

iterate_2()

のループ条件を変更すると、生成コードから剰余命令が除去されます。どのパスがこれを実現し、以前は機能しなかった理由は何か説明してください。

---

ケース 2：エンディアン変換

シナリオ

ほとんどのバイナリフォーマットは数値フィールドに特定のバイト順序を指定します。32 ビット値の場合、次のように書けます。

uint32_t load_le32(const uint8_t* data)
{
    return data[0] | (data[1] << 8) |
           (data[2] << 16) | (data[3] << 24);
}

uint32_t load_be32(const uint8_t* data)
{
    return data[3] | (data[2] << 8) |
           (data[1] << 16) | (data[0] << 24);
}

x86 上では最適なアセンブリが生成されます。

load_le32(unsigned char const*):
    mov eax, dword ptr [rdi]
    ret

load_be32(unsigned char const*):
    mov eax, dword ptr [rdi]
    bswap eax
    ret

汎用実装は次のようになります。

static uint64_t load(const uint8_t* data, size_t sz, bool be)
{
    uint64_t val = 0;
    for (size_t i = 0; i < sz; ++i)
        val |= static_cast<uint64_t>(data[be ? sz - i - 1 : i]) << (8 * i);
    return val;
}

sz==4

または

sz==8

で呼び出すと、上記の関数と同じものが得られます。コンパイルすると、まだ最適なロードが生成されることが確認できます。

命令選択

この最適化は命令選択（ISel）段階でのみ発生します。LLVM は IR を Machine IR（MIR）へ変換する際に SelectionDAG フレームワークを使用し、そこに DAGCombiner と呼ばれるペイホール最適化が存在します。

MatchLoadCombine()

メソッドは、複数の狭いロードを組み合わせて幅広いロード（必要ならバイトスワップ）へ折りたたむパターンを検出します。

// 幅広い型のスカラー値が複数の狭いロードでロードされ、シフトとORで結合されるパターンをマッチ。可能なら単一ロードまたはBSWAP付きロードへ折りたたむ。

メソッドは

calculateByteProvider()

を再帰的に追跡し、

or

命令の出力で各バイトがどこから来ているかを特定します。これにより次のような式も扱えます。

static uint64_t load_alt(const uint8_t* data, size_t sz, bool be)
{
    uint64_t val = 0;
    for (size_t i = 0; i < sz; ++i)
        val = (val << 8) | data[be ? i : sz - i - 1];
    return val;
}

ただし、このバージョンは DAG の再帰が深くなり、10 レベルというハードコードされた制限に達するため、32 ビット関数のみが完全に最適化されます。

コンパイラを助ける

ロード関数をテンプレート化すると：

template <size_t sz, bool be>
static uint64_t load(const uint8_t* data)
{
    uint64_t val = 0;
    for (size_t i = 0; i < sz; ++i)
        val |= static_cast<uint64_t>(data[be ? sz - i - 1 : i]) << (8 * i);
    return val;
}

IR は

AggressiveInstCombine

パスで単一ロードに最適化されます。これはよりまれなペイホール最適化を実行し、

-O2

のときのみ一度だけ走ります。

foldConsecutiveLoads()

関数は「ビット演算 OR + 省略可能左シフト + ゼロ拡張された連続ロード」のパターンにマッチします。

この最適化はターゲット非依存であるため、リトルエンディアンのターゲット上ではビッグエンディアンロードを折りたたみません。

並び替え、再検討

AggressiveInstCombine

は初期の非テンプレート版では実行されませんでした。なぜなら、パスが走る時点でループはまだ展開されていたからです。関数テンプレートは各テンプレート引数セットごとに別々にインスタンス化されるため、インライン化の前にループが完全に展開され、マッチ可能になります。

同じ結果を元のコードで得たい場合は次を実行します。

clang++ -S -emit-llvm -O2 -o- endianness.cpp |
opt -S -passes='aggressive-instcombine' - | llc --x86-asm-syntax=intel

---

演習 5

上記のように

load_alt()

をテンプレート化し、生成された出力を確認してください。以前と同じ結果になるか？ テンプレーティングが最適化パイプラインに与える影響は何ですか？

---

演習 6

エンディアンによってロード順序を変える代わりに、同じ順序でロードし、戻り値に対して

__builtin_bswap64()

をオプションで呼び出すことができます。これが

AggressiveInstCombine

の最適化能力にどう影響するか説明してください。

---

自分自身に足を踏み入れる

次のようなケースを考えてみましょう。

uint32_t load_le32(const uint8_t* data) { return load(data, 4, false); }

uint32_t load_add_le32(const uint8_t* data)
{
    return load_le32(data) + data[0];
}

期待されるコードはロード＋加算ですが、コンパイラは次のように生成します。

load_add_le32(unsigned char const*):
    movzx ecx, byte ptr [rdi]
    movzx edx, word ptr [rdi + 1]
    shl edx, 8
    movzx eax, byte ptr [rdi + 3]
    shl eax, 24
    or  eax, edx
    or  eax, ecx
    add eax, ecx
    ret

DAGCombiner は各バイトの起源を追跡し、重複ロードを避けます。

AggressiveInstCombine

も重複ロードを作成しません。この問題に対処するには、

load_le32()

内でテンプレート化された関数を呼び出し、

load_add_le32()

にインライン化される前に

AggressiveInstCombine

がループを最適化できるようにします。

---

演習 7

上記の例で

data[0]

の代わりに

val & 0xFF

を使用するとどうなるか、そしてなぜそうなるか説明してください。どんな小さな変更であらゆる関数呼び出しでも機能するようにできますか？

---

サイズ最適化

-Os

の場合、コンパイラはループ展開がコードサイズを増加させると判断し、ロードの折りたたみを行いません。

#pragma unroll

をループ前に付けたり、再帰テンプレートを書いたりすると最適化を促すことができます。

---

結論

主なポイント：

1. 意図を明示的にする – テンプレート、マクロ、属性を使いコンパイラにコンパイル時の事実を知らせる。
2. 早期最適化 – コンパイラが何かを早く最適化できれば、その後のパスでさらに恩恵が得られる。
3. よく知られたパターンに従う – 既存の最適化は多くの一般的構文をカバーしている。巧妙なトリックはあまり効果がない。

---

補遺：その他の資料

• LLVM公式ドキュメント
  • LLVM Language Reference Manual
  • LLVM Programmer’s Manual
  • The LLVM Target‑Independent Code Generator
  • LLVM Loop Terminology（および Canonical Forms）
• Nikita Popov のブログ
  • “LLVM: The middle‑end optimisation pipeline”
  • “LLVM: Canonicalisation and target-independence”
  • “LLVM: Scalar evolution”
• LLVM オプティマイザの風景を一望できる YouTube

---