Compiler Construction Lecture 10/22</h1>

Menu Menu

先週の復習


宿題の解答

BSD/OS上で、Sparc用のGCC cross compilerを作成し、それからSparc CPU上で動作するGCCを作成する手順を示せ。cross compiler とは コンパイラが動作する環境と、コンパイラが出力するコードの動作する環境が違うものをさす。

実行系の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"
という形test.s にcompileされる。これをgdbで実行するには、これをさらにcompileして、 
    gcc -g test.c
    gdb a.out
とする。 

    (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 <main>:       pushl  %ebp
    0x80483cd <main+1>:     movl   %esp,%ebp
    0x80483cf <main+3>:     movl   0x80494e4,%eax
    0x80483d4 <main+8>:     leave  
    0x80483d5 <main+9>:     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 *)&check; 
        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 について調べると良い。 

    main(int av,char *av[])
    {
        int i,j,k;
        i = atoi(av[1]);
        j = atoi(av[1]);
        j = i + j;
        return j;
    }
また、それらの計算がどう進むかをstep実行し、レジスタの中身を表示することによって示せ。 

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

    Subject: Practice on Compiler consturction Lecture 10/22
というサブジェクトで送ること。

Shinji KONO / Mon Oct 22 16:40:57 2001