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


2021-03-09 更新

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

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

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

info編集部注: スマートフォンでご覧の際は、アルゴリズムを横スクロールすると全文をご覧になれます

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

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

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

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

 

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

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

 

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

図 1 無駄があるプログラムの例
・A ← 123
・A ← 123
・Print(A)

このプログラムでは、

・A ← 123

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

図 2 無駄を排除したプログラムの例
・A ← 123
・Print(A)

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

図 3 さらに無駄を排除したプログラムの例
・Print(123)

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

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

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

図 4 無駄があるプログラムをインタプリタで実行した場合
・A ← 123     ・・・(1) この 1 行をマシン語に変換して実行する
・A ← 123     ・・・(2) この 1 行をマシン語に変換して実行する
・Print(A)    ・・・(3) この 1 行をマシン語に変換して実行する

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

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

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

問 19 平成 28 年度 春期 午前

コンパイラにおける最適化の説明として,適切なものはどれか。

オブジェクトコードを生成する代わりに,インタプリタ用の中間コードを生成する。
コンパイルを実施するコンピュータとは異なるアーキテクチャをもったコンピュータで動作するオブジェクトコードを生成する。
ソースコードを解析して,実行時の処理効率を高めたオブジェクトコードを生成する。
プログラムの実行時に,呼び出されたサブプログラム名やある時点での変数の内容を表示するようなオブジェクトコードを生成する。

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

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

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

解答

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

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

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

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

問 2 平成 24 年度 春期 午後(一部抜粋)

 コンパイラの最適化に関する次の記述を読んで,設問 1 ~ 3 に答えよ。

 コンパイラとは,プログラム言語で記述された原始プログラムを翻訳して目的プログラムを生成するためのソフトウェアである。コンパイラの機能の一つに最適化がある。最適化では,原始プログラムを翻訳する過程で,プログラムの実行時間を短くするために原始プログラムの構造を変換する。最適化の方法の例を表 1 に示す。
表 1 最適化の方法の例
最適化の方法 内容
関数のインライン展開 関数を呼び出す箇所に,呼び出される関数のプログラムを展開する。
共通部分式の削除 同じ式が複数の箇所に存在し,それらの式で使用している変数の値が変更されず,式の値が変化しないとき,その式の値を作業用変数に格納する文を追加し,複数の同じ式をその作業用変数で置き換える。
定数の畳込み プログラム中の定数同士の計算式を,その計算結果で置き換える。
定数伝播 変数を定数で置き換える。
無用命令の削除 プログラムの実行結果に影響しない文を削除する。
ループ内不変式の移動 ループ中で値の変化しない式があるとき,その式をループの外に移動する。
ループのアンローリング ループ中の繰返しの処理を展開する。

 擬似言語の形式で記述したプログラムの一部 (以下,プログラム 1 という) に対して,表 1 の最適化の方法を複数組み合わせて最適化した例を,表 2 に示す。

〔プログラム 1 〕

■ i : 0, i ≦ 1, 1
| • x[i] ← y[i] + m + n
| • v[i] ← w[1] + m + n
■
表 2 プログラム 1 の最適化の例
最適化の方法 プログラム 1 の変換
(1)
■ i : 0, i ≦ 1, 1
| ・ t ← m + n
| ・ x[i] ← y[i] + t
| ・ v[i] ← w[i] + t
■
(2)
・ t ← m + n
■ i : 0, i ≦ 1, 1
| ・ x[1] ← y[1] + t
| ・ v[1] ← w[1] + t
■
(3)
・ 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
次の記述中のに入れる正しい答えを,解答群の中から選べ。
表 2 において,最適化の方法を (1),(2),(3) の順で適用するとき, (2) で適用される最適化の方法はaであり, (2) で適用される最適化の方法はbである。

a, b に関する解答群
ア 関数のインライン展開  
イ 共通部分式の削除
ウ 定数の畳込み  
エ 定数伝播
オ 無用命令の削除  
カ ループ内不変式の移動
キ ループのアンローリング

前半部の設問 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
■
(1) で最適化した後のプログラム
■ 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) で最適化した後のプログラムを示します。

(1) で最適化した後のプログラム
■ i : 0, i ≦ 1, 1
| ・ t ← m + n
| ・ x[i] ← y[i] + t
| ・ v[i] ← w[i] + t
■
(2) で最適化した後のプログラム
・ 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) で最適化した後のプログラムを示します。

(2) で最適化した後のプログラム
・ t ← m + n
■ i : 0, i ≦ 1, 1
| ・ x[1] ← y[1] + t
| ・ v[1] ← w[1] + t
■
(3) で最適化した後のプログラム
・ 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 を解いてみましょう。

設問 3
次の記述中のに入れる適切な答えを,解答群の中から選べ。
最適化をしないときと最適化をしたときとで浮動小数点数の演算の結果が異なる場合がある。プログラム 1 に対して表 2 の最適化をしなかったものと,最適化 をしたものとに, y[0] = 3307000000.0, y[1] = 305000000.0, m = -303000000.0, n = 4.0 を与えて実行した。その結果の x[0], x[1] が次のとおりになった。ここで,同一優先順位の算術演算子は,左から順に演算する。

最適化をしないとき:
x[0] = 4000004.0, x[1] = 2000004.0
最適化をしたとき:
x[0] = 4000000.0, x[1] = 2000000.0

この実行結果が異なる原因としては,dの方法の適用によって演算順序が変化したことで,eが発生したからである。ここで,浮動小数点数の演算は単精度 (仮数部は 23 ビット) で計算しているものとする。

d に関する解答群

ア 関数のインライン展開  
イ 共通部分式の削除
ウ 定数の畳込み  
エ 定数伝播
オ 無用命令の削除  
カ ループ内不変式の移動
キ ループのアンローリング

e に関する解答群

ア 桁あふれ  イ 桁落ち  
ウ 情報落ち  エ 丸め誤差

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

最適化をしないときの 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) で最適化した後のプログラムです。

(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 の正解は、選択肢イです。

searchタグで関連記事をチェック情報落ち

 

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

いかがでしたか?

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

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

label 関連タグ
Q. 午前試験を
『免除』するには?
A. 独習ゼミで午前免除制度を活用しましょう。
免除試験を受けた 87% の方が、
1 年間の午前免除資格を得ています。
2022 年 上期 試験向け
コース申込を開始!
最大 10 % OFF の早割も!
info_outline
2022 年 上期 試験向け
コース申込を開始!
最大 10 % OFF の早割も!
詳しく見てみるplay_circle_filled
label これまでの『基本情報でわかるテクノロジー』の連載一覧 label 著者

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

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

主な著作物

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