基本情報でわかる コンパイラ 最適化

矢沢 久雄
2021-03-09 更新

この連載では、基本情報技術者試験によく出題されるテクノロジー関連の用語を、午前問題と午後問題のセットを使って解説します。

午前問題で用語の意味や概念を知り、午後問題で技術の活用方法を知ってください。それによって、単なる丸暗記では得られない明確さで、用語を理解できるようになります。

今回のテーマは、 コンパイラの最適化 です。

コンパイラの最適化とは？

プログラムを実行する方式には、大きく分けて インタプリタ と コンパイラ があります。

インタプリタは、プログラムの内容を 1 行ずつマシン語（コンピュータが直接理解できる命令）に逐次変換しながら逐次実行します。

コンパイラは、プログラムのすべての内容をマシン語に一括変換してから一括実行します。

インタプリタとコンパイラには、それぞれ長所と短所がありますが、今回のテーマである「最適化（ optimization ）」は、コンパイラの長所です。

最適化とは、プログラムをマシン語に一括変換するときに、プログラムの中にある無駄を排除することです。これによって、プログラムの実行速度を向上させたり、プログラムのサイズを小さくしたりできます。

たとえば、図 1 に示した 3 行のプログラムがあるとしましょう。ここでは、基本情報技術者試験の擬似言語でプログラムを記述しています。Printは、引数の値を画面に表示する関数だとします。

・A ← 123
・A ← 123
・Print(A)

このプログラムでは、

・A ← 123

という同じ処理（変数 A に 123 という適当な値を代入する処理）が、わざとですが、 2 回記述されています。同じ処理を 2 回記述することは無駄なことなので、コンパイラは、プログラムの内容を図 2 であると解釈して、マシン語に変換します。 ・A ← 123という処理を 1 回だけにしていることが最適化です。

・A ← 123
・Print(A)

さらに、コンパイラは、「このプログラムは、画面に 123 を表示できればよいのだから、変数 A を使うことは無駄である」と解釈して、図 3 に示したように最適化します。画面に 123 を表示する・Print(123)という処理だけになりました。

・Print(123)

コンパイラに最適化ができるのは、プログラムのすべての内容を見てからマシン語に変換するからです。すべてを見れば、無駄があることがわかります。

それに対して、インタプリタには、最適化ができません。なぜなら、プログラムの内容を 1 行ずつ見ているので、無駄があることがわからないからです。

たとえば、先ほど図 1 に示した 3 行のプログラムをインタプリタで実行すると、図 4 の (1), (2), (3) の順に、逐次変換されて、逐次実行されます。

・A ← 123     ・・・(1) この 1 行をマシン語に変換して実行する
・A ← 123     ・・・(2) この 1 行をマシン語に変換して実行する
・Print(A)    ・・・(3) この 1 行をマシン語に変換して実行する

コンパイラの最適化 に関する午前問題

コンパイラの最適化の意味がわかったところで、午前問題を解いてみましょう。以下に問題を示します。

選択肢の中にある「オブジェクトコード」とは、マシン語のことです。「ソースコード」とは、マシン語に変換される前のプログラムのことです。

ソースコードを解析して、実行時の処理効率を高めたオブジェクトコートを生成する

と説明している選択肢ウが正解です。

その他の選択肢が何の説明であるかは、気にしないでください。他のツールの説明の場合もありますが、まったくデタラメの場合もあるからです。

解答ウ

コンパイラの最適化に関する午後問題（最適化の具体例）

以下は、コンパイラの最適化に関する午後問題を一部抜粋したものです。

他の記事でも書きましたが「基本情報技術者試験は、実によくできているなあ！」と思います。この問題の前半部では、コンパイラの最適化の様々な具体例を示しています。そして、後半部では、コンパイラの最適化の弊害を示しています。

つまり、コンパイラの最適化は、確かに便利ではあっても、いいことづくめではない、ということを示しているのです。この問題によって、コンパイラの最適化を深く理解できます。

■ i : 0, i ≦ 1, 1
| • x[i] ← y[i] + m + n
| • v[i] ← w[1] + m + n
■

■ i : 0, i ≦ 1, 1
| ･ t ← m + n
| ･ x[i] ← y[i] + t
| ･ v[i] ← w[i] + t
■

･ t ← m + n
■ i : 0, i ≦ 1, 1
| ･ x[1] ← y[1] + t
| ･ v[1] ← w[1] + t
■

･ t ← m + n
･ x[0] ← y[0] + t
･ v[0] ← w[0] + t
･ x[1] - y[1] + t
･ v[1] - w[1] + t
･ i ← 2

前半部の設問 1 を解いてみましょう。

表 1 に最適化の方法の具体例が示されていて、表 2 の (2) と (3) で適用されている方法が、どの方法に該当するかを答える問題です。せっかくなので、表 2 の (1) から説明しましょう。最適化は、(1) → (2) → (3) の順に進んで行くからです。

以下に、最適化する前のプログラムと、 (1) で最適化した後のプログラムを示します。

■ i : 0, i ≦ 1, 1
| • x[i] ← y[i] + m + n
| • v[i] ← w[1] + m + n
■

■ i : 0, i ≦ 1, 1
| ･ t ← m + n
| ･ x[i] ← y[i] + t
| ･ v[i] ← w[i] + t
■

繰り返し処理の中で、同じm + nという加算が 2 回行われています。これは、無駄なことです。

そこで、・t ← m + nという処理を追加して加算結果を変数 t に代入し、これまでのm + nの部分をtに置き換えています。これによって、加算は 1 回だけになります。

これは、表 1 の中で

同じ式が複数の個所に存在し、それらの式で使用している変数の値が変更されず、式の値が変化しないとき、その式の値を作業用変数に格納する文を追加し、複数の同じ式をその作業用変数で置き換える

に該当するので、「共通部分式の削除」です。ここでは、 t が作業用変数です。

以下に、 (1) で最適化した後のプログラムと、 (2) で最適化した後のプログラムを示します。

■ i : 0, i ≦ 1, 1
| ･ t ← m + n
| ･ x[i] ← y[i] + t
| ･ v[i] ← w[i] + t
■

･ t ← m + n
■ i : 0, i ≦ 1, 1
| ･ x[1] ← y[1] + t
| ･ v[1] ← w[1] + t
■

・t ← m + nにおいて、 m + n の演算結果と、変数 t に代入される値は、繰り返し処理の中で、常に同じです。同じ演算と代入を繰り返すのは、無駄なことです。

そこで、・t ← m + nを繰り返しの外に出しています。

これは、表 1 の中で

ループ中で値の変化しない式があるとき、その式をループの外に移動する

に該当するので、「ループ内不変式の移動」です。したがって、空欄 a の正解は、選択肢カです。ループ（ loop ）とは、「繰り返し」という意味です。

以下に、 (2) で最適化した後のプログラムと、 (3) で最適化した後のプログラムを示します。

･ t ← m + n
■ i : 0, i ≦ 1, 1
| ･ x[1] ← y[1] + t
| ･ v[1] ← w[1] + t
■

･ t ← m + n
･ x[0] ← y[0] + t
･ v[0] ← w[0] + t
･ x[1] - y[1] + t
･ v[1] - w[1] + t
･ i ← 2

■ i：0, i ≦ 1, 1という構文を使った繰り返し処理は、 2 回の繰り返しを行います。たった 2 回の繰り返しのために、変数 i を 0 に初期化し、i ≦ 1というチェックと変数 i に 1 を加算する処理を毎回行うのは、無駄なことです。

そこで、■ i：0, i ≦ 1, 1という構文を使った繰り返しをやめて、 2 回の処理を、そのまま記述しています。プログラムが長くなりましたが、変数 i に関する処理がなくなったので、実行速度は速くなります。

これは、表 1 の中で

ループ中の繰り返しの処理を展開する

に該当するので、「ループのアンローリング」です。したがって、空欄 b の正解は、選択肢キです。

コンパイラの最適化に関する午後問題（最適化の弊害）

設問 2 は省略して、後半部の設問 3 を解いてみましょう。

この設問の内容は、「最適化をしたら、浮動小数点数の演算の結果に誤差が生じてしまった」ということです。

最適化をしないときの　x[0] = 4000004.0 と x[1] = 2000004.0 は、正しい値です。

それに対して、最適化をしたときの x[0] = 4000000.0 と x[1] = 2000000.0 では、 4.0 の部分が失われて、誤差が生じています。

これは、浮動小数点数において、大きな値と小さな値を加算または減算すると、大きな値の指数に合わせて演算されるので、小さな値が 0 になってしまう（情報が消えてしまう）、という誤差であり、情報落ちと呼ばれます。

したがって、空欄 e の正解は、選択肢ウです。

ここでは、 y[0] = 307000000.0, y[1] = 305000000.0, m = -303000000.0, n = 4.0 なので、 y[0], y[1], m が大きな値であり、 n が小さな値です。

問題文に

同一優先順位の算術演算子は、左から順に演算する

とあるので、最適化をしたことによって、演算の順序が変わってしまい、大きな値と小さな値の加算または減算が生じたのです。

以下は、最適化する前のプログラム（最適化をしないときのプログラム）です。

■ i : 0, i ≦ 1, 1
| • x[i] ← y[i] + m + n
| • v[i] ← w[1] + m + n
■

・x[i] ← y[i] + m + nという演算では、まず、 y[i] と m という大きな値どうしの加算が行われ、その結果として小さな値が得られます。

次に、その小さな値と n という小さな値どうしの加算が行われます。これなら、情報落ちは生じません。これは、・v[i] ← w[i] + m + nの部分でも同様です。

以下は、 (1) で最適化した後のプログラムです。

■ i : 0, i ≦ 1, 1
| ･ t ← m + n
| ･ x[i] ← y[i] + t
| ･ v[i] ← w[i] + t
■

問題の前半部で説明した「共通部分式の削除」という方法で、・t ← m + nという処理を行っています。

これは、 m という大きな値と、 n という小さな値の加算なので、情報落ちが生じる場合があります。

したがって、空欄 d の正解は、選択肢イです。

解答設問 1　a – カ, b – キ　設問 3　d – イ, e – ウ

いかがでしたか？

午前問題と午後問題のセットで、コンパイラの最適化を、しっかりと理解できたでしょう。

この連載では、今後も、多くの受験者が苦手としている用語を取り上げて行きます。それでは、またお会いしましょう！

基本情報でわかる IPアドレス と サブネットマスク

update 2021-12-02

基本情報でわかる ホワイトボックステスト

update 2021-03-10

基本情報でわかる トランザクション

update 2021-02-25

基本情報でわかる コンパイラ 最適化

update 2021-03-09

基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる」

update 2021-01-25

基本情報でわかる 浮動小数点 「3つの情報で1つの数を表す仕組みを知れば、浮動小数点数がわかる」

update 2021-12-03

基本情報でわかる MIME タイプ 「電子メールの仕組みを知れば役割がわかる」

update 2021-12-02

基本情報でわかる 7セグメントLED 「 1 と 0 を書き込めば点灯するパターンがわかる」

update 2021-12-02

基本情報でわかる 論理演算 「真理値表を書けば、半加算器と全加算器の仕組みがわかる」

update 2021-12-16

基本情報でわかる SMTP ／ POP3 「ITエンジニア視点で見れば役割がわかる」

update 2021-12-02

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数