2005-04-23

近況

よっぱらって帰宅しウェブをみたら, GCC4.0 がリリースされていた. GCC の開発速度は目覚ましい. 魔窟なようなコードがハッカーを挑発するからか. 変更履歴 に C++ の項目は多く, この言語が stable からほど遠いことがわかる. C++ を仕事で使いたいという憧れは強いけれど, 本当に使うならコンパイラ限定, OS 限定, ライブラリ限定という制限つきでないと嫌だな. 最適化されるはず, というコードは信用できない. 最適化されたコードだけが信用できるから.

それはさておき, 高速化のキーワードに知らないものが多い. 私はコンパイラの勉強をしたことがないから仕方ないけれど, なんとなく悔しい. せめてわかった気になりたいから Google してみることにする. それにアプリケーションプログラマだって, コンパイラが何をしてくれるかを知っておいて損はない.

以下に列挙した最適化のキーワードは changes.html から. どれもが GCC4.0 から入った新機能ではなく, こういう最適化もしていますよ, というもの.

Scalar replacement of aggregates

構造体のフィールドを普通の変数のように扱うこと. レジスタ割当とかで有利になる, らしい. 構造体の変数が複数あった時に, 構造体まるごとではなくフィールド単位でレジスタに割当てをしてくれるということか. なんとなく当り前に思えるけど, 今までやってなかったのかな...印象より大変なのかもしれない.

Constant propagation

演算の結果を追跡して, 定数として扱える変数を定数にするというもの. オフラインで計算しマジックナンバーとしてソースコードに埋め込んでいたところを, ソースコードに計算過程ごと書けるようになると. 便利そう.

Value range propagation

上のに似ているけれど, もうちょっと大変そう. ある変数のとりうる値を絞りこんでおき, それを利用した最適化をするというものらしい. たとえば, switch や if などの分岐で絶対に通らないパスを削除できたり, 分岐そのものを排除できたりする. 絶対通らないパスなんで作らずに assert しておけという気もする. 実際は他にも有用なケースがあるのかもしれない.

Partial redundancy elimination

よくわからない. まず redundancy elimination というのがあって, これは冗長な計算(同じ式の評価)を削除して結果を再利用するというものらしい. 演算というと四則演算とか関数呼出しみたいのを連想するけれど, よくあるオブジェクト参照連鎖 (foo.bar.baz() みたいの) も eliminate されるので嬉しい.

で, 式の一部分から冗長な部分を抜きだしてくれるのが partial redundancy elimination ということか. partial でない redundancy elimination はあまり嬉しくない気がする. Google で検索しても, "partial redundancy elimination" の方がよくひっかかる.

Load and store motion

load とか store 命令を loop の外側におしだしてくれる, とのこと. ループ内で参照してループの外に押し出せる変数(つまりループ内では定数な値)なんてレジスタに載りそうなものだけれど, 巨大なループでは有効か. 命令レベルの最適化の話はよくわからない.

Strength reduction

これはよく聞くやつ. 重い計算を軽い計算に置きかえるというもので, Dragon Book にも載っているらしい.

Dead store elimination

これは名前から想像がつく, 参照しない変数への保存はスキップするというもの. 有難味の度合は不明.

Dead and unreachable code elimination

これも名前どおり.

Autovectorization

これは比較的最近の話題らしい. C のコードを CPU の並列命令 (SSE, Maltivec) にマップしてくれるというもの. 具体的にどんなコードが並列化されるのは自明でない. 文書を読まないとわからない. 単純な for ループでできそうはものはしてくれる, らしい. グラフィクスプログラマはこういうのを意識して書くとかなり嬉しい気がする.

Loop interchange

ネストしたループの入れ子関係に細工したり, 外部に押し出せるものを押し出すなどする高速化. 行列の掛け算などで効くという. アプリケーションプログラマは既存の枯れたライブラリを使うのが吉ではあるが, これから GCC を使ってその手の線型代数ライブラリを書く人はいいかもしれない. 私には, 具体的に何がおこるのか直感的に把握できない.

Tail recursion by accumulation

tail recursion は lisp の一味で有名な最適化, 再起呼出しをループになおす. "by accumulation" が何なのかはわからない.

Swing Modulo Scheduling

さっぱりわからない. 記事を読んでもわからなそうなので挫折する. パイプラインを意識した高速化なんだろうか. これを意識したコードを書く, という種類のものでもないからわからなくても困らないのだけれど, こうさっぱりわからないと悲しい.

資料を眺めていると, ここには非常に高度なテクノロジーと大量の実装資源が投入されていることがわかる. 奇特なグルが物好きでメンテナンスしている枯れた技術だと思っていたけれど, 企業の研究所なども contribute している. GCC はオープンソース・プロジェクトのバックエンドであると同時に, 最前線のオープンソース・プロジェクトなのだなあ. 感動.

参考資料