コード最適化

最適化とは、効率のよい目的プログラムを生成することである。

「効率のよい」
とはいろいろな意味がある。例えば、なるべくサイズの小さいコードを 生成するのも「効率のよい」と意味にもなる。コードを小さくするためには、 なるべく小さい命令コードですむスタックマシン（大抵、１バイトで表現され るためバイトコードとも呼ばれる）にし、それを仮想スタックマシンで実行す る方法もこの一つである。しかし、一般的には「効率のよい」とは、速いコー ド、すなわち実行時間が短いコードのことをいう。また、「最適化」といって いるが、「最適」は事実上、不可能であるため、ここではなるべく効率を改善 するという意味である。

実行時間を短くするには、大別して以下のことを考える

  1. 命令の実行回数を減らす。より早い命令（もしくは命令の組み合わせ）を使う。
  2. メモリ階層を効率的に使う。
  3. 並列度の高い命令を使う。
命令の数を減らしても必ずしも、速いとはいえない。RISCマシンでは大抵 の命令は一定のサイクル（１サイクル？）で実行されるために命令数を減らす ことは実行時間の短縮になるが、CISCマシンではそうはいえない。命令数 を減らす最適化は、基本的には無駄な計算を取り除くことである。例えば、ルー プ内で同じ計算している場合には、これをループの外で計算することによって、 大幅に命令数を減らすことができる。

現在のマイクロプロセッサはレジスタ、キャッシュ（１次、２次）、メモリ、 そしてディスクというメモリ階層をもっている。特にコンパイラではレジスタ を効率的に使うことは重要な最適化になっている。もっと進んだコンパイラで は、ループの実行順序を入れ替えて、なるべくキャッシュを効率的に使う最適 化を行うものもある。

プロセッサの中で命令は並列に実行されるのが普通である。現在のマイクロプ ロセッサではスーパースケラ（SuperScalar）機構があるが、この機構を効率 的に使うために命令をいれ変える。また、数値計算を効率的に行うベクトルマ シンに対しては、この機構を利用するコードを生成するが、これも並列度を持 つ命令を使う最適化の一つである。

コンパイラで最も重要な最適化は、ループに関する最適化である。このルー プ最適化は上に挙げた最適化の組み合わせで行われる。多くのプログラムで、 比較的小さい部分が実行時間のほとんどを占めるといわれている。つまり、数 個のループを最適化することで実行時間を多くを改善することができる。

コンパイラでできない（できることもある？）最適化は、アルゴリズムの最 適化である。例えば、ソートする部分をバブルソートからもっとよいquickソー トにするだけで大幅に性能が改善する。しかし、バブルソートから自動的に quickソートに変換することはコンパイラではできない。コンパイラは、ひど いアルゴリズムを救うことはできない。このような最適化はプログラムの本質 の部分であり、プログラマの力量が問われるところでもある。

命令の実行回数を減らす最適化

命令の実行回数を減らす最適化は以下のものがある。

  1. １度計算した結果を再利用する。（共通部分式の削除）
  2. コンパイル時に実行できるものは実行（計算）しておく。（定数の畳込み）
  3. 命令をより、実行頻度が低い部分に移す。（ループ最適化：ループ不変式の削除）
  4. 実行回数を減らすように、プログラムを変換する。（ループ変換）
  5. 式の性質を利用して、実行を省略する。（帰納変数の削除、演算子の強さの低減）
  6. 冗長な命令を取り除く。（死んだコードの削除、複写の削除）
  7. 特殊化する。（手続き呼び出しの展開、判定の展開）

共通部分式の削除(common sub-expression elimination) 

a=b+c;　　　 (1)
 ....
x = (b+c)*e; (2)
というコードがあった時に、b+cに関して、 (1)が先に実行されていて、(1)から(2)の間にb+cが変わらない時、(2)のb+cは、 aに置き換えることができる。これを、 共通部分式の削除 という。

定数の畳込み(constant folding)、定数伝播(constant propagation) 

a=3+4   (1)
....
b = a*2  (2)
に対して、(1)をa=7にしてしまう最適化を、 定数の畳み込みと呼ぶ。 共通部分式の削除と同様に、(1)の後に(2)が実行され、(1)から(2)の間にaの値がかわ らなければ、 b=14にしてしまうことができる。この最適化を、定数伝播と呼 ぶ。

ループ不変式の削除（loop invariant motion） 

for(i=0; i < 10; i++){
    ....  
    a=b*c; 
    ... 
}
ループのなかで、bとcの値が変わらなければ、a=b*cは、ループの外に出しておくことできる。 
a=b*c;
for(i=0; i < 10; i++){
    ....  
    ... 
}
ループ内で変わらない式を ループ不変式で、これをみつけ移動する こと(code motion)をループ不変式の削除という。このた めには、ループ 内で、代入されていなく、かつ関数呼び出しがあった場合そこでも代入されて いないことを確かめる必要がある。

帰納変数の削除(reduction variable elimination)、 演算子の強さの低減(strength reduction) 

for(i=0; i < 10; i++){
    .... 
    k = 10*i+123; 
    ... 
}
ループを制御するiのような変数をループ変数（loop variable）と 呼ぶ。ループ内に、i=i+cしか代入がない変数を基本帰納変数(basic induction variable)という。ループ変数は、基本帰納変数である。この基本 帰納変数に対し、帰納変数(reduction variable)とは、基本帰納変 数もしくは、 変数に代入されるたびにiの線形の関数になる変数である。kは帰納変数である。

この帰納変数に対し、 

k=123;
for(i=0; i < 10; i++){
    .... 
    k = k+10; 
    ... 
}
と変形できる。この場合、i*10という乗算を加算というより簡単な演算に変形 しているが、これを演算子の 強さの低減(strength reduction) と 呼ぶ。一般に乗算よりも加算は速く 実行できるので、効率的になる。この最適化は帰納変数 x に対し、線形の計算 a*x+bに適用できる最適化である。

Ｃ言語では配列を使った計算を 

for(i = 0; i < 10; i++){ 
    .... 
    x = a[i]; 
    ...
}
と書くことができるが、この最適化を使って 
p = a; 
for(i = 0; i < 10; i++){ 
   .... 
   x = *p; 
   ... 
   p++; 
}
と変形され、余計なアドレス計算を削除する最適化が行われれることがある。 多次元配列などについては、そのままコード生成すると乗算が必要となるが、 この最適化で加算のみで計算されるようになる。

なお、演算子の強さの軽減とは、一般的にはx*2をx+xとしたり、x**2(べき乗) をx*xとしたり、より簡単な演算に置き換えることをいう。

ループ展開(loop unrolling)、ループ融合(loop fusion) 

 for(i = 0; i < 100; i++){  
   a[i]= ...; 
}
について、これを刻み幅を2にして、 
 for(i = 0; i < 100; i+=2){ 
   a[i]=....; 
   a[i+1]=...
}
にすることをループ展開という。これにより、条件判定が半分にな るほか、ループ内のレジスタの割り当てが効率的になることがある。

また、 

for(i = 0; i < 10; i++){ 
     .... a[i] = ...; ...
}
 for(i = 0; i < 10; i++){ 
     .... b[i] = ...; ...
}
を 
 for(i = 0; i < 10; i++){ 
    ... a[i] = ...; ...
    ... b[i] = ...; ...
}
としてしまうことをループ融合という。この場合、ループ間でデー タの依存がないことを確認しなくてはならない。

死んだ命令の削除(dead code elimination)

不要な命令をdead codeという。例えば、 

... goto L;
x = ...
L: ...
では、xへの代入は実行されない。この場合はdead codeであり、削除できる。また、 
x=100;   (1)
 ...
x = i+j;  (2)
というように、(1)の後に(2)が実行され、(1)から(2)の間にxが使われなければ、(1)は不要な命令であり、削除できる。

複写の伝播(copy propagation) 

a= b; (1)
...
 c=a+d; (2)
で、(1)の後に(2)が実行され、aもｂも代入されなければ、(2)は、c=b+dにす ることができる。これを複写の伝播という。

コードの巻き上げ(code hosting) 

if(...) { 
   ... 
   T=a+b; 
   ...
} else { 
    ...; 
    T=a+b; 
    ...
}
のように、分岐先で同じ計算をする場合、 
T=a*b; 
if(...) { 
  ...
} else { 
  ...
}
とコードを移動することを コードの巻き上げ(code hosting)という。

手続き呼び出しの特殊化、式の性質の利用 

foo(i)
{  
   if(i < 10) return i+2; 
   else return i*2;
}
という関数呼び出しに対して 
x = foo(5);
のfooを展開して、 
　{  i= 5; if(i < 10) x= i+2; else x=i*2;}
さらに、x=7としてしまうことができる。

また、 

if(a && b) x = 100;
で、aがtrueであることがわかれば、条件を取りぞのいて、 
x=100;
にしてしまうことができる。 また、x*1はx,　y+0は、yというように式の性質を利用して計算を省略できる。