Compiler Construction Lecture 10/25

Compiler Construction Lecture 10/25

先週の復習



問題1

GCC は以下の手順で生成される IとTを使って、以下のコンパイルを図示せよ (I-T図)

実行系のArchitecture

Compilerのtargetにはいろいろあるが、あるComputer上でもっとも高速なのは、 そのComputerのmachine language(機械語)である。したがって、machine language がもっとも重要なCompiler targetだということができる。ここでは、いくつかの CPUのProgramming Modelを学び、その実行を調べる方法を学ぶ。

CPUのprogramming modelは、以下の要素からなる。

個々のCPUには、それぞれ特徴があり、compilerを作る際にはその特徴を 考慮する必要がある。しかし、極端に異なるachitecutreを持っているものは 少なく、どれをとっても同じようなものだともいうことができる。

すべてのCPUに詳しくなる必要はないが、どれか一つの専門家にはなって いたい所である。


Little-Endian, Big-Endian

Computer には memory がつきものだが、memory は、1 byte (= 8bit) 単位でlinear address (byte addressing) がふられている。しか し、最近のCPUは、16bit, 32bit, 64bit 単位(word)で処理をおこ なう。従って、wordをどのように byte addressing に割り振る(map) かという問題がある。これには主に2種類の mapping があり、それ ぞれLittle-Endian, Big-Endian と呼ばれている。

どちらが優れているかという議論はあったが、現在では卵のとがっている 方から割るか、丸い方から割るかぐらいの違いしかないと認識されている ようだ。


もう、このmappingは、CPU - memory 間の転送も考慮する必要がある。 同じ 1 word を転送するのでも、Busが64bit幅だったりすれば、その アドレス下位3bitの値によって、一回で転送できる場合とそうでない 場合がある。これを word alignment の問題という。当然、一回で 転送できる方が高速に動作する。

これらの問題は、普通のプログラミングでは考える必要はないが、 効率の良いMachine Languageを生成する場合には考慮する必要が ある。


Addressing Mode

実際にCPUとmemoryのdataのやり取りをするのが、load/store 系の命令 である。CPUの命令の中で大きな割合を占める。Addressing modeとは、 register や命令で、どのように memory address を指定するかを決める 方法である。昔は、MC6809のように豊富なIndex modeを持つものが 歓迎された。今では、RISC Architecture という、simple な Address mode を持つ命令が好まれている。

現在のプログラミングでは、配列(array)やリスト(list)、構造体(structure) のアクセスが重要なので、Addressing mode は、それを1命令で実現しやすい ように設計されているのが普通だ。だいたい図のようなAddressing mode を採用しているものが多い。





いろいろなCPUのProgramming Model

Intel x86 32bit mode

現在もっとも良く使われているCPU。しかし、16bit modeを使っている所も 多いだろう。ここでは、比較的きれいなarchitectureを持っている32bit mode のみを紹介する。

8bit CPU(8080)の拡張によってできたCPUなので、32bit modeでも それをかなり引きずっている。命令は8bitの可変長命 令である。80386によって、16bit/32bit切替と仮想記憶がサポート され爆発的な成功を納めた。最近のPentinum II では、内部でRISC 命令に変換してから実行するというようなことをしている。16bit ではregisterの役割が偏っていたが、32bitでは若干対称性が良く なっている。4本のAccumulator、4本のIndex register を持つ。

Addressing modeには以下のようなものがある。 

 Immediate                        movb al,$F0     constantをloadする
 extended                         movb al,[$F000] 指定されたaddressからloadする
 indexed                          movb al,[EAX+5] indexとoffsetで示されたaddress からload する
 accumulator offset indexed       mov [EBX+EAX]
 accumulator offset indexed       mov [EBX+EAX+5]
さらに、x86には segement register というのがあり、それによっ てvirtual memory (メモリ空間) を切り替えることができる。しか し、普通はすべて同じメモリ空間が設定されている。他のCPUでも データ(data)とコード(code)は別空間にできるものが多い。

演算はレジスタとレジスタの間で行うことが多い。 もう少し詳しくは、インテル386のアセンブラ を参照すること。





MIPS

MIPS社が開発した、典型的なRISC CPU。NEC や Sony のWorkstationに 採用されたが、一番有名なのは、 Silicon Graphics 社の SGI だろう。 MIPS は現在はSGIに買収されている。また、Playstationや任天堂のN64 にも使われている。

非常に簡潔なアーキテクチャであるが、branchの後の一命令を実行する delayed slotをもっている。これは今では既に時代遅れだと言える。 むしろ、MIPSは、大域的なレジスタ割り当てを持つコンパイラ技術が 注目された。32本の汎用レジスタを持つが、半分を大域的な変数に 割り当てることが可能である。





Sparc

SunがMotorolaのMC680x0の後継として採用したRISC CPU。富士通や TIが生産を行っている。Overrapped Register WindowとDelayed Branch が売り物だったが、残念ながらその技術は今では評価は低い。

Overrapped Register Windowは subroutine callの度に多数(7つか ら20程度)のregister fileを切り替える。register fileがいっぱ いになると、割り込みがかかりstackに書き出す。この処理が重い ので、compilerはregister file の切替をできるだけ遅らせなくて はならない。これは、register windowの狙いからすると本末転倒 である。save, restore 命令によりregister windowを切り替える ことになっている。

Delayed branch は、PowerPCと同様にbranchの際のパイプラインの 乱れを避けるためのもので、branchをすることになって一命令 だけbranchの次の命令を実行する。これを行うかどうかを指定する bit が opcode の中に存在する。しかし、一命令だけでパイプラインが 乱れないというわけでもなく、compiler が面倒をみるということならば、 PowerPCと同様のことをしなければならない。これも失敗した技術 だということができるだろう。

Addressing modeには以下のようなものがある。 

 %g0                           %g0 は0に固定されている
 register addressing           ld 3,%r0  indexとoffsetで示されたaddress からload する
 register addressing           ld %r5,%r0
Immediate addressing はなく、PowerPCと同様である。set, sethi という 疑似命令が用意されている。これはorで実現されている。演算はPowerPCと 同様3引き数である。





ここでは取り上げなかったが、 CompaqのAlpha CPU, HPのPA-RISC なども良くできたCPUである。

どのように学ぶのか

Unix のC compiler には、-S option があり、Assembelr sourceを 生成することができる。簡単なCのプログラムを書いてcompileして 見るとどんな命令が生成されるかがわかる。

IBMPC は、pw上でcompile すれば良い。Sparc は、nirai, kanai 上でcompileすれば良い。MIPS は、PlayStation 用のcross compiler を使用する。 /usr/open/lectures/kono/compiler/mc-intel に太田昌宏氏による Micro-C を i386 用に修正したものがある。

gdb というdebuggerを使って、そのAssemberの実行を一命令づつ 調べることができる。 

int a[10];
main() 
{
    return a[4];
}
は、gcc -O -S test.c によって、(RISCの場合は-Oを付けた方がより 分かりやすいコードがでることが多い) 
        .file   "test.c"
        .version        "01.01"
gcc2_compiled.:
.text
        .align 4
.globl main
        .type    main,@function
main:
        pushl %ebp
        movl %esp,%ebp
        movl a+16,%eax
        leave
        ret
.Lfe1:
        .size    main,.Lfe1-main
        .comm   a,40,4
        .ident  "GCC: (GNU) 2.8.1"
という形にcompileされる。これをgdbで実行するには、 
(gdb) b main
Breakpoint 1 at 0x80483cf: file test.c, line 4.
(gdb) r
Starting program: /local/kono/public_html/lecture/1999/compiler/99-10-25/a.out 

Breakpoint 1, main () at test.c:4
4           return a[4];
(gdb) disass
Dump of assembler code for function main:
0x80483cc 
:       pushl  %ebp
0x80483cd :     movl   %esp,%ebp
0x80483cf :     movl   0x80494e4,%eax
0x80483d4 :     leave  
0x80483d5 :     ret    
End of assembler dump.
(gdb) stepi
5       }
(gdb) stepi
0x80483d5 in main () at test.c:5
5       }
(gdb) p $eax
$1 = 0
(gdb)
とすれば良い。



問題

以下のprogram check_endian.c がある。 

int check = 0x12345678;
main()
{
    char i, *ptr;
    
    ptr = (char *)✓ 
    i = ptr[1];
    return i;
}
このprogramをcompileしたassemblerを、i386, Sparc, MIPS のうち、少なくとも 2つ のCPUで表示 させて見よ。また、gdb で i にどのような値が入るかを 確認せよ。そのCPUは、Little-Endian か Big-Endian かを答えよ。 また、 trace の結果を、確認せよ。

Endian の変換はどのような時に必要になるか。どのようにすれば 実現できるか?

Unix には、Builtin のEndianの変換関数がある。 それを探し出せ。また、その実装がどうなっているかを調べよ。 (ヒント: man -k を使う)


宿題

Cの 様々な整数演算が、どのようなアセンブラにコンパイラによって変換されるか を -S フラグを使って調べよ。(最低、4則演算については調べること) singed, unsigned について調べると良い。

また、それらの計算がどう進むかをstep実行し、レジスタの中身を表示する ことによって示せ。 

Subject: Report on Compiler consturction Lecture 10/25
というSubjectのメールにして、kono@ie.u-ryukyu.ac.jp まで送ること。 また授業を受けなかったものは、課題を、 
Subject: Practice on Compiler consturction Lecture 10/25
というサブジェクトで送ること。

Kono's home page http://bw-www.ie.u-ryukyu.ac.jp/~kono/