Compiler Construction Lecture 10/21

先週の復習

問題1

以下のプログラムがある。
• Cで書かれた6809 上で動作するプログラム -- A
• Cで書かれた6809 code を動作させる emulator -- E
• Cで書かれた6809 codeを生成するC compiler -- C09
• RS6000上ののC compiler -- CC
IとTを使って、以下のコンパイルを図示せよ
• A をRS6000上でtestする状況を図示せよ。
• 6809上で動作する予定のCで書かれたプログラムを 6809 code emulator を使って、 RS6000でtestするという状況を図示せよ。
• 6809上でAをcompileできるcompilerを作成する手順をする。

実行系のArchitecture

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

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

• Registers
• Instruction
  • load, store instruction メモリからデータを取り出す、格納する
  • addressing mode レジスタからアドレスを計算する
  • arithmetic 数値演算
  • branch instruction jumpやsubroutine call、条件分岐
  • etc その他
個々の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

Motorola MC6809

「究極の8bit CPU」とかいわれたCPU。OS-9というOSに合わせて開発されて いる。8bit CPUにしては珍しく、2つのAccumulator, 4つのIndex Register を持つ。

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

 Immediate                        LDA #$F0      constantをloadする
 extended                         LDA $F000     指定されたaddressからloadする
 indexed                          LDA 5,X       indexとoffsetで示されたaddress からload する
 accumulator offset indexed       LDA A,X
 indexed + post increment         LDA A,X+      loadしたあと X を一つ増やす
 indexed + pre decrement          LDA A,-X      loadする前に X を一つ減らす

さらに、これらを一段間接にしたindirect addressing も用意されている。 演算は、基本的にaccumulatorとmemory間で行われる。






Intel x86 32bit mode

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

8bit CPU(8080)の拡張によってできたCPUなので、32bit modeでも それをかなり引きずっている。命令はMC6809と同じ8bitの可変長命 令である。80386によって、16bit/32bit切替と仮想記憶がサポート され爆発的な成功を納めた。最近のPentinumPro では、内部で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)は別空間にできるものが多い。

演算はレジスタとレジスタの間で行うことが多い。










PowerPC

現在、琉球大で使われているRS6000のCPUの後継機。Macintosh に 採用された。IBMはRISCの開発元であり、4命令の同時実行など最高 の技術が使われている。が、複雑なバスを要求すること、思ったよ りCPUのclockが速くならなかったことなどが影響して、Macintosh のbreak throughにはなりえなかった。Motorola は MC68000 series の拡張にも失敗しており、IBMとの共同プロジェクトであった、PowerPC により、さらにCPUメーカとしての汚名を広げたといえる。が、CPU 技術的には現在最高のものであることには変わりがない。

RISC CPUの特徴として32bit 固定長命令を採用している。またパイ プライン処理が深いために、分岐命令のかなり前に(3命令程度) そ の分岐の方向が決まるようにプログラムしないと処理速度が落ちて しまう。Subroutine callは、LR (link register) CTR (count register) 経由で行われるので、単純な一命令にはならない。並列実行される 命令が多いのでコンパイラはそれを考慮したコードを生成しなければ ならないなど、コンパイルは難しいがやりがいがあるCPUでもある。

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

 D形式                         lbz  RT, D (RA)  indexとoffsetで示されたaddress からload する
 X形式                         lbzx RT, RA,RB   RA+RBで示されたaddress からload する
 D形式 with update             lbzu RT, D (RA)  RAがRA+Dになる点が違う
 X形式 with update             lbzux RT, RA,RB  RAがRA+RBになる点が違う

Immediate addressing はなく、足し算命令を代わりに使う。これにより命令数 を減らしているわけである。さらにEndianを変換しながらload/storeする命令も ある。演算は、3引き数であり、r0に3をたしてr5に入れるなどということが できる。










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引き数である。






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

どのように学ぶのか

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

PowerPC は、bw, cw 上でcompile すれば良い。Sparc は、fish1, fish2 上でcompileすれば良い。Intel x86は、hyde でcompileすれ ば良い。MC6809のcompilerとemulatorは、 /usr/open/lectures/kono/compiler/mc に太田昌宏氏によるcompilerと、 /usr/open/lectures/kono/compiler/util09 にBenschopによる6809 emulatorがある。

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

int a[10];
main() 
{
    return a[4];
}

は、cc -O -S test.c によって、(RISCの場合は-Oを付けた方がより 分かりやすいコードがでることが多い)

.main:                                  # 0x00000000 (H.10.NO_SYMBOL)
        .file   "test.c"                
        l       r3,T.22.a(RTOC)
        l       r3,16(r3)
        bcr     BO_ALWAYS,CR0_LT

という形にcompileされる。(一部だけ抜きだしている。実際には、その他の 部分がたくさんある) これをdbxで実行するには、

% cc -g test.c
% dbx a.out
(dbx) stop in main
[1] stop in main
(dbx) run
[1] stopped in main at line 5
    5       return a[4];
(dbx) stepi
stopped in main at 0x1000047c
0x1000047c (main+0x4) 80630010          l   r3,0x10(r3)
(dbx) registers
  $r0: 0xdeadbeef  $stkp: 0x2ff7f910   $toc: 0x2005285c    $r3: 0x20052880  
  $r4: 0x2ff7f950    $r5: 0x2ff7f958    $r6: 0xdeadbeef    $r7: 0x2ff7fffc  
  $r8: 0x00000000    $r9: 0x20052874   $r10: 0xdeadbeef   $r11: 0xdeadbeef  
 $r12: 0xdeadbeef   $r13: 0xdeadbeef   $r14: 0xdeadbeef   $r15: 0xdeadbeef  
 $r16: 0xdeadbeef   $r17: 0xdeadbeef   $r18: 0x20052600   $r19: 0xdeadbeef  
 $r20: 0xdeadbeef   $r21: 0xdeadbeef   $r22: 0xdeadbeef   $r23: 0xdeadbeef  
 $r24: 0xdeadbeef   $r25: 0xdeadbeef   $r26: 0xdeadbeef   $r27: 0xdeadbeef  
 $r28: 0xdeadbeef   $r29: 0xdeadbeef   $r30: 0xdeadbeef   $r31: 0xdeadbeef  
 $iar: 0x1000047c   $msr: 0x0002d0b0    $cr: 0x28222880  $link: 0x1000042c  
 $ctr: 0xdeadbeef   $xer: 0x20000000    $mq: 0xdeadbeef   $tid: 0x00000000  
          Condition status = 0:e 1:l 2:e 3:e 4:e 5:l 6:l 
        [unset $noflregs to view floating point registers]
in main at 0x1000047c
0x1000047c (main+0x4) 80630010          l   r3,0x10(r3)
(dbx) q

とすれば良い。まず、cc でコンパイルして、dbx をa.outに対して起動している。 main に break point を置いて実行したのち、1命令づつ実行する stepi を 行っている。registerの内容は、registers command で確認できる。

MC6809の場合は、 /usr/open/lectures/kono/compiler/mc/mc test.c とする。すると、c.out というファイルにassemblerが出力される。

a       EQU     0
main
        PSHS    U
        LEAU    ,S
        LDD     8,Y
        SYNC
        PULS    U,PC
_1      RTS
_INITIALIZE     EQU     _1
_GLOBALS        EQU     20
        END

という感じになる。このままでは止まらないので、PULSの前にSYNCという 命令を入れてある。これを以下のようにassembleする。

   /usr/open/lectures/kono/compiler/util09/a09 c.out

すると、c というファイルができる。これを、

   /usr/open/lectures/kono/compiler/util09/v09t c 

として実行の様子を見ることができる。

宿題2

以下のprogram check_endian.c がある。

int check = 0x12345678;
main()
{
    char i, *ptr;
    
    ptr = (char *)✓ 
    i = ptr[1];
    return i;
}

このprogramをcompileしたassemblerを、どれか一つのCPUで表示 させて見よ。また、dbx で i にどのような値が入るかをstepi で確認せよ。そのCPUは、Little-Endian か Big-Endian かを答えよ。 また、 trace の結果を、

Subject: compiler lecture 10/21

というSubjectのメールにして、kono@ie.u-ryukyu.ac.jp まで送ること。