ループ不変量コード移動

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ループ不変量コード移動" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年1月)

ループ不変量コード移動（るーぷふへんりょうこーどいどう、英: Loop-invariant code motion, LICM） とは、ループの内部の文脈に依存しない命令をループの外に移す最適化手法である。

例

以下のKotlinで書かれたソースコードを考える。

fun calculate(n: Int, factor: Int): Int {
  var sum = 0
  var i = 0
  while (i < n) {
    val r = factor * 2
    sum += r
    i++
  }
  return sum
}

変数 r の値 factor * 2 は、ループ変数 i の変化に依存せず、ループの反復ごとに同じ値をとる。そのため、この計算をループの外に移動させても意味論は変わらない。

ただし、ループが一度も実行されない場合（n <= 0 の場合）を考慮し、副作用や不要な演算の発生を防ぐ安全性を担保するため、条件分岐を伴う形に最適化される。

次に、最適化が施された後のコードを提示する。

fun calculate(n: Int, factor: Int): Int {
  var sum = 0
  var i = 0
  if (i < n) {
    val r = factor * 2
    do {
      sum += r
      i++
    } while (i < n)
  }
  return sum
}

これにより、ループが実行されるたびに毎回行われていた重複した計算を削減しつつ、ループ非実行時の安全性を維持してパフォーマンスを向上させることができる。