前号の補足

　前号で抜けがあったオプションを説明します．

● -fsched-spec-load，-fsched-spec-load -dangerous

　このオプションを指定すると，命令をロードする際に，順序を最適化することを許可します．ただし，-fschedule-insnsオプションか-o2オプションの付加が必要です．

静的単一代入形式について

　GCCはまずCソースを中間言語（RTL）に変換し，その後でアセンブラに変換を行います．そして，内部でアセンブリを行います．

　その中間言語の段階で構文解析を行い，最適化が行われます．また，ハードウェアに依存する最適化も行われます．

　デバッグ・オプションで説明しますが，-drを付加してコンパイルすると***.rtlというソース・ファイルが作成されます．これが中間言語のソースです．

　それぞれのファイルの例を，リスト1〜リスト3に示します．

　この場合GCC内部ではフロントエンドが中間言語（RTL）を生成し，バックエンドがRTLからアセンブラ・コードを生成します．

　RTLの段階では，CPUに依存しません．RTLを理解できる人はここで手動による最適化を行ってもかまいません．

　GCCでは，C言語以外にもJavaやFortranなどが扱えますが，RTLを作るまでがフロントエンドの仕事で，各言語に依存しますが，それ以降は共通の処理となります．

　なお，ネット上でRTLをインタプリタとして動作させるツールがありました．作者のページが見つからなかったのですが，
　　http://morihyphen.hp.infoseek.co.jp/files/asdf.tar.gz
からダウンロードできます．これを使って手動による最適化の効果を試すことができるはずです． 　さて，実際に静的単一代入形式（SSA）を使った最適化について説明します．

　　a = x + 2;
　　a = a + 1;
　　b = x + 2;

　上のような命令をSSA形式に変換すると次のようになります．

　　a1 = x0 + 2;
　　a2 = a1 + 1;
　　b1 = x0 + 2;

　これは変数の定義が唯一になるように変数の名前を付け直しているわけです．変数aは通常の場合，一つのアドレスに収められる変数ですが，SSA形式に変換すると代入した数だけ，変数aが作られます．それによって共通部分式除去などの一般的最適化が容易になり，効率も上がるということです．

　SSAを使用した最適化について簡単に説明します．

● コピー伝播

　簡単に説明すると，何度もaをbに代入しているコードがあった場合，最後のものだけを生かす手法です．ただし，途中でbの内容を変更後に参照するような場合には，そのままにします．

　リスト4のようなソースがあった場合，3か所にあるaをbに代入しているコードは最後のものだけ必要になります．

　しかし，リスト5のようなソースの場合には，そのような最適化はできません．return Foo(b);のために一番最初のb = a;を残す必要があります．

● 共通部分式除去

　aとbを演算した結果をcとします．その後，a，b，cが共に値が変わらないのであれば，再度同じ演算をして別の変数dに入れるような処理を廃し，cをdに代入することで解決させます．

　リスト6に示すコード�@〜�Cは，リスト7のように置き換えることができます．この場合，�Cの式は不要になります．もちろんコード�@〜�Cの間で，変数a〜eのアドレスに依存する処理を行っていたり，変数a〜eがCPUの記憶領域外にある場合には，そのようなことはできません．

　これをSSA形式で表すと次のようになります．

　　�@a0　=　b0　*　c0
　　�Ad0　=　b0
　　�Be0　=　a0
　　�Ca1　=　a0

● 効率的な質問伝播の拡張

　SSA形式では，プログラム中で同じ名前をもつ変数は同じ値をもつことが保証されていますが，ある式の値があるプログラム点において利用可能かどうかの判断は必要になります．

　ある式がある時点で有効かどうかの判断は，その式を後に追跡していくことで可能になります．「質問伝播」とは，その手法のことを言います．

● 無用コード除去

　実行されないコードは無用コードとなります．

　ブロックの中で無条件分岐の先にあるコードや，return文の後は無用コードとなります．

● 条件分岐を考慮した定数伝播

　定数伝播を行う方式には，コードのすべてを通るものとして考え，結果として条件文による分岐を考慮しない単純なアルゴリズムと，条件分岐を考慮したアルゴリズムが存在します．

　しかし，それでは現実に即さない最適化になってしまいます．「条件分岐」を考慮する場合には，より多く通るブロックで考えなくてはなりません．

● 空の基本ブロックの除去

　たとえば，

　　if(…)
　　　{
　　　}

のようなブロックを除去します．

　しかしif文の条件式が複文である場合など，除去できない場合もあります．

● ループ不変式のループ外追い出し

　非常にわかりやすい最適化ですが，リスト8のようなコードを，リスト9のように置き換えてむだな処理を除去します．

　以上のような最適化をSSAに基づいて行います．

　では，実際にソース（リスト10）をコンパイルしてみます．

　最適化なしのアセンブラ・ソースをリスト11に，最適化したアセンブラ・ソースをリスト12に示します．

　　$ gcc test236.c -O3 -fssa -S
　　$ cp test236.s test236a.s
　　$ gcc test236.c -O3  -S
　また，次のようにしてRTLを出力します．
　　$ gcc test236.c -O3 -fssa -dr
　　$ cp test236.c.00.rtl  test236.c.01.rtl
　　$ gcc test236.c -O3  -dr

　結果は長くなるので省略しますが，RTLソースを見比べれば最適化がなされていることがわかります．コピー伝播によって不用なコードの除去が行われているはずです．

　GCC3.5以降でないと正式なものではありませんが，静的単一代入形式について理解してこの最適化を使用すると，良い結果が出ることもあります．この最適化に挑戦してみてください．

連載インデックス　｜　次のページ

記事内インデックス　　　　連載インデックスはこちら　　　Interfaceのトップ

◆静的単一代入形式による最適化 ◆リスト