先週は、以下のことを勉強した。
SPARCでは、変わった呼び出し方をしている。SPARCには overraped register window というのがあり、それぞれ、%i,%l,%o というように区別されている。 それぞれ8本ずつある。call すると、caller の %o が、callee の%i となる。 これを引数渡しに使う。(したがって8個以上の引数はregister渡しにできない。 実際にはframe pointerやstack pointerがあるので、もっと少ない) また、浮動小数点には、regisger windowはない。 calleeからcallerに戻る時には、再び%iが%oとなる。これによって値を 返すことができる。この切替えは、save/restore という命令によって おこなわれる。
この方法の良いところは、stackにいちいち値をcopyしなくても済むところ である。しかし、register windowは無限にあるわけではないので、いつかは いっぱいになってしまう。その時にはsub routineを呼び出して、register windowの中身をスタックにcopyする。copyした後、戻る時には、また、スタック からregister windowにcopyする。実際のアプリケーションでは、この register window overflowが頻繁に起きるので、 残念ながら、この方法が成功しているとは いえなかったようである。
実際には以下のような呼び出しを用いる。
mov 4,%g3
call _print,0
mov %g3,%o0 callより、こちらが先に実行される
L1:
ret
restore register window をもとにもどす
.align 8
.global _print
.proc 04
_print:
!#PROLOGUE# 0
save %sp,-104,%sp register window の切替え
!#PROLOGUE# 1
st %i0,[%fp+68] %i0にcallerの%o0が入っている
sethi %hi(LC0),%o1
or %o1,%lo(LC0),%o0
ld [%fp+68],%o1
ld [%fp+68],%o2
call _printf,0 この呼び出しはregister windowを使わない
nop
L2:
ret
restore ret より先にこちらが実行される
call の後にある、,0 と、nop は、Delayed Slot と呼ばれるもの である。昔のSparc は、jump や、call の際に、一つだけそのアド レスを先読みすることにより、パイプラインの乱れを吸収していた。 ここにコンパイラがnopではなく、実際の命令を置くことにより、 パイプラインを乱すことなく計算を続けることができる。
しかし、今のCPU技術では、命令の先読みは数命令に渡っており、 1つのDelayed Slotではパイプラインの吸収しきれない。代わって、 分岐予測が重要となっている。例えば、call文などでは、call 先が呼ばれることがわかっているので、先読みは、そちらを 行えば良い。ここでもSPARCのRISCの技術は残念ながら失敗している。
また、PowerPCなどでは、分岐を判断するフラグを分岐命令よりも 前に確定させることにより的確な先読みを可能にしている。フラグの 確定を先に持って行くのは、コンパイラの責任である。
これまでは、式(expression)単位のコンパイルを考えてきた。このコンパイルは、 直接的で簡単である。レジスタの数の少ない6809では最適に近いコードを出力 ることができる。しかし、最適化(optimize)を考える時、特にレジスタの数の 多いRISCの場合は、これではレジスタを有効利用しているとはいえない。
式の単位での最適化と、式を越えた大域的な最適化を考えるために、 基本ブロック(Basic Block)とフローグラフ(Flow Graph)というものが 工夫された。
基本単位は、単純に言えば、条件分岐や分岐を含まない逐次計算の 部分である。フローグラフは、一つの手続の中で基本ブロックを分 岐を結んだものである。
mc.c の reverse() はリストを逆順にするものだが、
484 reverse(t1)
485 int t1;
486 {int t2,t3;
487 t2=t1;
488 while(type!=t1)
489 { t3=cadr(type);
490 rplacad(type,t2);
491 t2=type;
492 type=t3;
493 }
494 type=t2;
495 }
このcadr()とかrplcad()は
2840 cadr(e)
2841 int e;
2842 { return heap[e+1];
2843 }
2894 rplacad(e,n)
2895 int e,n;
2896 { heap[e+1]=n;
2897 return e;
2898 }
である。すると、
484 reverse(t1)
485 int t1;
486 {int t2,t3;
487 t2=t1;
488 while(type!=t1)
489 { t3=heap[type+1];
490 heap[type+1]=t2;
491 t2=type;
492 type=t3;
493 }
494 type=t2;
495 }
としてよい。
このフローグラフを考えてみよう。 このフローグラフ(flow graph)を作るには、まず基本ブロック(basic block) を抜きだす。基本ブロックは、分岐(barch)の入らない部分 のまとまりをさす。次に、flow-chart のように基本ブロックを接 続する。あと、入力される変数と、出力される変数を記述する。
flow-chart と違い、基本ブロックは最適化の単位となるので、可
能な限り一つにまとめなければならない。結果は以下のようになる。
基本ブロック内部では条件分岐がないので、文(statement)の実行 順序(execution order)をプログラムの意味を変えない範囲で変更 してコンパイルして良い。これは局所的最適化と呼ばれる。
基本ブロックの間で再利用出来る式、計算する必要のない式、ある いは、使わない変数などを見つけると、それらを共有したり、削っ たりすることができる。さらに、簡単なループの場合は内部の基本 ブロックの定数などをループの外に出すことも行われる。これらは 大域的最適化と呼ばれる。これらが終わると、変数にレジスタを割 り当てる(register allocation)。RISCでは、このレジスタの割り 当て方法が重要である。
基本ブロックの最適化では共通の式などを抜きだす。このためには、 基本ブロックの中の式を一度、DAG グラフ(Directed Acyclic Graph) に直すのが良い。
DAGの作り方
以下のプログラムのDAGを作成せよ。できれば、作成したDAGにした がってi386 のアセンブラを作成せよ。
A: a=b+c; b=a-d; c=b+c; d=a-d; B: a=b+c; b=b-d; c=c+d; e=b+c; C: e=a+b; f=e-c; g=f*d; h=a+b; i=i-c; j=i+g;ヒント。単にグラフの形だけでなく、式の意味を考えて共通部分式と しても良い。
局所的最適化の代表的なものは peep hole optimization と呼ばれ るものである。これはいったんコードを生成した後に、そのコード を狭い範囲で見て、より良いものに置き換えられるならば置き換え るというものである。共通部分式の置き換えなどはできないが、簡 単で効果的であることが知られている。コード生成の時点で行って しまっても良い。例えば、micro-C ではそうなっている。
問題1のアセンブラに落すのを宿題にします。