末尾再帰以外の再帰除去とループ変換

末尾以外の再帰をどうループに落とすか

末尾再帰は、戻った後にやることが無いのでループへ機械的に書き換えられました。問題は末尾でない再帰です。代表例は分割統治や木の走査で、子を再帰した後に親で集計が残ります。これらは「戻り先での処理」がある以上、単純なループにはなりません。

手段は二つあります。一つは明示的スタックを用意し、処理系のコールスタックが担っていた「中断地点と未処理の作業」を自前のデータ構造（配列）へ移す方法です。再帰そのものを消すわけではなく、暗黙のスタックを可視化して反復に変えます。

// 二分木の中順走査を明示スタックで反復化
iter_inorder(root):
  stack = []
  node = root
  while node != null or stack not empty:
    while node != null:        // 左の枝を限界まで降りて積む
      stack.push(node)
      node = node.left
    node = stack.pop()         // 戻る＝未処理だった親を取り出す
    visit(node)
    node = node.right          // 右の枝へ

もう一つは、可能なら累算器で計算順序を前倒しし、末尾再帰へ整形してからループ化する方法です。和や積のように結合的な集計なら、戻ってから足す代わりに引数へ畳み込めば末尾化できます。ただし木の構造やグラフのように分岐が二つ以上ある走査は累算器では平らにできず、明示スタックが定石になります。

ループ不変式の巻き上げ（LICM）

ループ本体に「毎回同じ値になる計算」が紛れていると、反復回数ぶんだけ同じ仕事を繰り返します。これをループの外へ追い出すのが**ループ不変式の巻き上げ(LICM / Loop-Invariant Code Motion)**です。

// 巻き上げ前：len(a) と base*2 を毎回計算
for i in 0 .. len(a):
  a[i] = a[i] + base*2 + len(a)

// 巻き上げ後：ループ内で変わらない計算を前に出す
n = len(a)
k = base*2 + n
for i in 0 .. n:
  a[i] = a[i] + k

ある式がループ不変である条件は、その式が依存する変数すべてがループ本体で再代入されないことです。上のbaseやlen(a)は反復で変わらないので、計算結果をループ外の一時変数に固定できます。判定はコンパイラ内部ではデータフロー解析で行われ、各変数の定義がループの中にあるか外にあるかを追跡します。

展開・融合・交換・タイリング：順序だけを変える

ここからは結果を一切変えず、実行順序や反復構造だけを変形するループ変換です。意味が同じでも、分岐の回数やメモリアクセスの順番が変わり、性能が大きく動きます。

ループ展開は、for iの本体を例えば4回ぶん並べ、iを4ずつ進めます。ループ回数が1/4になるので、終了判定とカウンタ更新の分岐コストが減り、隣り合う独立した4命令をCPUが同時実行（命令レベル並列）しやすくなります。さらに同種演算が並ぶことで、後述のSIMD化の足場にもなります。

// 展開前
for i in 0 .. n:
  s += a[i]

// 4段展開（n が4の倍数の場合。端数は別ループで処理）
for i in 0 .. n step 4:
  s += a[i] + a[i+1] + a[i+2] + a[i+3]

ループ融合は、for i: b[i]=a[i]*2とfor i: c[i]=b[i]+1のように同じ範囲を別々に回す処理を一つにまとめ、a[i]やb[i]を二度ロードする無駄を消します。逆方向の分割は、ベクトル化を妨げる依存だけを別ループに切り出して、残りを並列化可能にする目的で使います。

交換とタイリングが局所性を引き出す原理

ループ変換の効果が最も劇的に出るのが、メモリアクセス順序を変える交換とタイリングです。ここはCPUキャッシュの動作を理解すると腑に落ちます。

二次元配列は多くの言語で行優先(row-major)、つまり同じ行の要素がメモリ上で連続しています。ところが内側ループで列方向に進むと、一歩ごとに行サイズぶん飛んだアドレスを触り、キャッシュラインを使い切る前に捨ててしまいます。内外を入れ替えて連続方向に走るだけで、同じ計算が数倍速くなります。

// 悪い順序：内側 i が列方向に飛ぶ（行優先配列で非連続アクセス）
for j in 0 .. N:
  for i in 0 .. N:
    sum += A[i][j]

// 交換後：内側 j が連続方向（同一キャッシュラインを使い切る）
for i in 0 .. N:
  for j in 0 .. N:
    sum += A[i][j]

**タイリング（ブロック化）**は、大きな配列を一度に舐めるとキャッシュから溢れる問題を、小ブロックに区切って各ブロックを集中的に再利用することで解決します。行列積が典型で、N×Nを丸ごと回すと一方の行列を毎回キャッシュ外から読み直しますが、B×Bのタイルに分ければそのタイルがキャッシュに居座る間に何度も使い回せます。

// 行列積をタイル幅 B でブロック化（作業集合をキャッシュに収める）
for ii in 0 .. N step B:
  for jj in 0 .. N step B:
    for kk in 0 .. N step B:
      for i in ii .. ii+B:
        for j in jj .. jj+B:
          for k in kk .. kk+B:
            C[i][j] += A[i][k] * B[k][j]

変換の安全性は「依存」が決める

これらの変換を勝手に施してよいわけではありません。許されるかどうかはデータ依存で決まります。反復iが書いた値を反復i+kが読む、といった依存があると、順序を変えると結果が変わってしまいます。

各反復が完全に独立（依存なし）なら、コンパイラやCPUは安心して順序を入れ替え、複数反復をまとめてSIMD命令で一括処理できます。これがベクトル化です。逆にa[i] = a[i-1] + 1のように前の反復の結果に依存すると、並列化もベクトル化も原理的に阻まれます。SSA形式と最適化を持つ最適化器は、この依存をデータフローとして正確に追い、安全な変換だけを選びます。

まとめ

末尾でない再帰の除去は、コールスタックが暗黙に持っていた「未処理の仕事」を明示的スタックへ移すか、累算器で計算順序を前倒しして末尾再帰に整形するかの二択です。木やグラフの走査は前者が定石になります。

ループ変換の核心は「結果を変えずに実行順序だけを変える」点にあります。不変式の巻き上げは反復ごとの無駄な再計算を消し、展開は分岐削減とSIMDの足場を作り、交換とタイリングはメモリアクセスをキャッシュに優しい順序へ整えて局所性を引き出します。これらが許されるかは反復間のデータ依存とエイリアスで決まり、依存が無いほど展開・交換・並列化・ベクトル化の自由度が上がります。同じアルゴリズム・同じ計算量でも、走査順を整えるだけで実機の速度が桁で変わる——ここが計算量の理論だけでは見えない、実装最適化の勘所です。