Swiftの中間言語SILを読む その6 - シンプルなCommon-subexpression Elimination

February 22, 2018

DCEの次はCommon-subexpression Eliminationを実装してみる。 Swiftのレポジトリでいうとこの辺り。

Common-subexpression elimination(CSE) 概要

wikipediaなどでは「共通部分式除去」と訳されていて、簡単にいうとプログラムの複数の文の中に共通する部分があったらそれをまとめて置き換えてしまおうという最適化である。

SILにおいてはDCEと同様SILFunctionを一つの単位として、その中で共通の部分があれば置き換えていく。以下の例であれば%0%1の右辺がInt8の8を作っていて、全く同じである。

sil @test0 : $@convention(thin) () -> (Builtin.Int8, Builtin.Int8, Builtin.Int16, Builtin.Int8) {
    %0 = integer_literal $Builtin.Int8, 8 // ここと
    %1 = integer_literal $Builtin.Int8, 8 // ここが同じ
    %2 = integer_literal $Builtin.Int16, 8
    %3 = integer_literal $Builtin.Int8, 1
    %4 = tuple(%0 : $Builtin.Int8, %1 : $Builtin.Int8, %2 : $Builtin.Int16, %3 : $Builtin.Int8)
    return %4 : $(Builtin.Int8, Builtin.Int8, Builtin.Int16, Builtin.Int8)
}

この場合%1は必要なく、Optimzerは%1 = …の文を消した上で%1%0に置き換えて変数の名前付けを整理し、以下のようなSILを吐き出す。

sil @test0 : $@convention(thin) () -> (Builtin.Int8, Builtin.Int8, Builtin.Int16, Builtin.Int8) {
    %0 = integer_literal $Builtin.Int8, 8
    %1 = integer_literal $Builtin.Int16, 8
    %2 = integer_literal $Builtin.Int8, 1
    %3 = tuple(%0 : $Builtin.Int8, %0 : $Builtin.Int8, %1 : $Builtin.Int16, %2 : $Builtin.Int8)
    return %3 : $(Builtin.Int8, Builtin.Int8, Builtin.Int16, Builtin.Int8)
}

まずはアルゴリズムを定義する上で必要なAvailable expression(利用可能式)という概念を定義する。

Available expression(利用可能式)

制御フローグラフのentry nodeからあるノードnに至る経路で、式x ⊕ yが少なくとも1度計算され、かつその経路上でx ⊕ yの最近の出現以降でxやyの定義が存在しないならばx ⊕ yはノードnで利用可能(available)である。 (Modern compiler implementation in MLより)

これはSILのようなSSA形式に限らず一般的なプログラムに対する定義で、「かつその経路上でx ⊕ yの最近の出現以降で〜」の部分で以下のようなケースへの考慮が入っている。

a = x + y  // x + yが計算された!
x = ...    // しかしxが更新されたので
b = x + y  // こことは共通化できない

こういうケースを含め最適化を行うためには一般的にはgen集合・kill集合と呼ばれる「どの式が利用できてできないか」を解析して行く必要がある。 (解説略)

一方SILの場合は変数(%1など)が更新されることはなく、さらに右辺には1つの命令しか来ないためsubexpression = 右辺そのものとなるため、定義は少しシンプルにできる。

つまりSILの場合、「その式以前でsome_inst %x, %yが出現していればその式においてsome_inst %x, %yは利用可能」と言ってしまって良さそう。

また、すべてのsubexpressionが共通化できるわけではない。共通化を行うことによって当然呼び出し回数も呼び出し箇所も変わってしまうため、副作用のある命令などはCSEでは扱えない。

SILのCSEでどの命令が扱えるかは canHandle関数を参照。

CSEのアルゴリズム

利用可能式を使ってSILOptimizerにおけるCSEのアルゴリズムは以下のように定義できる。

  • ある文(sil-instruction-def)の右辺がその文で利用可能であれば、その左辺の変数(sil-value)の関数中の出現をすべて利用可能式を最初に定義した変数で置き換える。

シンプルですね! CSEのメインロジックの実装部分でまさにそんな実装になってます。

sil-opt-scalaでの実装

こちら。 https://github.com/ukitaka/sil-opt-scala/pull/1

(ライブラリとしての)LLVMはこのあたりの実装に使えるデータ構造が多く提供されているので、最適化書く人にとってはとても便利そうだなというのを実感した。ScopedHashTableとか。

まとめ

とりあえずシンプルなケースのCSEを実装した。ここで「シンプルなケース」と言ったのはopen_existential_xxx系の命令に対する最適化が別途扱われているためである。次回はそれを実装してみる。

このエントリーをはてなブックマークに追加