Compiler Construction Lecture 10/22</h1>

# 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は、以下の要素からなる。

Registers
program counter
stack, frame pointer
index
data
condition code
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

### 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

というサブジェクトで送ること。

Compiler Construction Lecture 10/22</h1>

先週の復習
宿題の解答
実行系のArchitecture
Little-Endian, Big-Endian
Addressing Mode
いろいろなCPUのProgramming Model
Intel x86 32bit mode
* インテル386のアセンブラ
MIPS
Sparc
コンパイラ出力を読む
* test.c によって、(RISCの場合は-Oを付けた方がより
* test.s
問題
宿題

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