Compiler Construction Lecture 10/29
Menu Menu来週、11/5, 11/12 の授業はお休みとします。
先週の復習
先週はさまざまなCPUのレジスタアーキテクチャ(Register architecture)について学んだ。
例えば Intel 386 ならば、
このようなレジスタを持っている。そして、 これ がアセンブラの命令表である。
i386のアセンブラ
i386 は比較的、対称性に欠ける命令体系を持ち、レジスタも少ない。しかし、可変長の命令を持つので、コードが若干コンパクトになるという特徴がある。アドレッシングモードも少ない。例えば、
negl %eax レジスタEAXのnegativeを取る
negl a 大域変数aのnegative を取る
negl (%eax) レジスタEAXの指すメモリのnegativeを取る
negl (%ebx+%eax) EAX+EBXの指すメモリのnegativeを取る
間接参照には、さらにオフセットを付けることができる
negl 4(%eax) レジスタEAXの指すメモリから4byteずれたところのnegativeを取る
negl 4(%ebx+%eax) EAX+EBXの指すメモリから4byteずれたところのnegativeを取る
問題1
i386はlittle-endianであり、メモリにはメモリのアドレスが小さい方に、 数値の小さい桁から格納される。また、%eaxレジスタは、高い方の桁が8bit %ahレジスタ、低い方の桁が8bit レジスタ%alとなっている。以下の数値は16進表記とする。
メモリの内容が以下のようになっているとき、
0000100: 23
0000101: 45
0000102: 56
0000103: 78
0000104: 90
0000105: 12
- movl 0x100,%eaxは、memory 0x100 の値を%eaxレジスタに格納する。この命令を実行した時、 %eaxレジスタの値はいくつになるか? %ahレジスタは? %alレジスタは?
- movl $0x100,%ebxは、0x100 の値を%ebxレジスタに格納する。
- %ebx レジスタが、0x100の時に、movl (%ebx),%eax を実行すると %eax レジスタの値は?
- incl %ebx を実行したあとに、movl (%ebx),%eax を実行すると %eax レジスタの値は?
- その後、movl 4(%ebx+%eax),%ecx を実行すると %ecx レジスタの値はどのアドレスのメモリからロード(取得)されるか?
- movb 2(%ebx),%al を実行すると %eax レジスタの値はどうなるか?
- movsbl 2(%ebx),%eax を実行すると %eax レジスタの値はどうなるか?
- movsbl 4(%ebx),%eax を実行すると %eax レジスタの値はどうなるか?
- leal 8(%ebx+%eax),%ecx を実行すると %ecx レジスタの値は?
さらにgdbの使い方を追求する
BSD/OS の gdb の man ページには、ほとんどなんの記述もない。その代わりに、info ページが充実している。mule の info か、または、info コマンドを用いて、GDB の情報を調べてみよ。gdb には、i386 のレジスタ一覧を表示する機能はない。gdb のaliases 機能を用いて、gdb にその機能を追加するには、
define regs
printf "%%eip=%08x: %%eax=%08x %%ebx=%08x %%ecx=%08x %%edx=%08x %%edi=%08x %%esi=%08x %%ebp=%08x %%esp=%08x\n", $eip,$eax,$ebx,$ecx,$edx,$edi,$esi,$ebp,$esp
end
を.gdbinitに追加する。
stepi
disass $eip $eip+1
は何をするコマンドが調べよ。
アセンブラのシングルステップが便利になるようなaliasを定義してみよ。
アセンブラ(Assembler)を使った計算
i386では、基本的に演算は、register to register で行われる。ここでは、以下のプログラムを使おう。
int a=4,b=3;
main()
{
a = a+1-(b-123);
return a;
}
これを gcc -S でコンパイルしてみると、.s というファイルに以下の内容がかかれる。(コメントはでないが...)
.file "tmp.c"
.version "01.01"
gcc2_compiled.:
.globl a
.data
.align 4
.type a,@object
.size a,4
a:
.long 4
.globl b
.align 4
.type b,@object
.size b,4
b:
.long 3
.text
.align 4
.globl main
.type main,@function
main:
pushl %ebp
movl %esp,%ebp
movl b,%eax # 変数bの値を %eax にロードする
addl $-124,%eax # -124 を %eax に加算する
movl a,%edx # 変数aの値を %edx にロードする
subl %eax,%edx # %edx から %eax の内容を引く
movl %edx,%eax # %edx の内容を %eax に移す
movl %eax,a # %eax の値を変数aに格納(ストア)する
leave
ret
.Lfe1:
.size main,.Lfe1-main
.ident "GCC: (GNU) 2.8.1"
となる。a: などが大域変数の場所を表している。
問2
a = 5+(6+(7+b));
をコンパイルした結果はどうなるかを、自分の頭で考えて示せ。
a = 0+(1+(2+(3+(4+(5+(6+(7+b)))))))-(0+(1+(2+(3+(4+(5+(6+(7+b))))))));
は、どうなるだろうか?
自分が、どのように考えて、その結果を出したのか、そして、それをアルゴリズムにするにはどうすれば良いのかを考えよう。
ヒント
まず式を木の形に書いて、構造を調べる
push, pop を使ってスタックを使う方法もある
実際のコンパイラの出力と比較してみよう。
問2
上のプログラムをIntel CPU上で、gcc -O -S test.c を使ってコンパイルすると最適化がかかる。最適化した場合としない場合で、どのような違いが出るか? (ヒント diff を使うと簡単...)問1で、これらの結果を実際のアセンブラで実行しテストするには、どうすれば良いか考えて実行せよ。
これらの命令が実際に生成されるCのソースコードを考えて、それをコンパイラに通し、実際に命令が生成されることを確認せよ。(ただし、データのアドレスは、変わっても良いとする)
Tokenizer 字句解析
手で木に変換する
いままでに出た式を木に変換して見よう。- 3-(4-2)
- 0+(1+(3-2))-(0+(1+(2-3)))
まず必要なのは、木にする時の一番基本的な単位を決めることである。これは単語の切り分けという。または、Tokenize 字句解析という。Tokenize するプログラムをTokenizer または、字句解析器という。
字句解析のルールは簡単で、
- 数字の続き
- 一文字の英字
- その他の記号((+,-,*,/,>)
- [0-9][0-9]*
- [a-zA-Z]
- [()=+-*/> ]
Tokenizer は、通常、そのtokenの型(type)と値(value)を返す。プログラムは、 この ような感じになる。
実際には、適当な状態遷移(state transition)を作ってやれば良い。より複雑な例は、また、あとで見ることにしよう。
このプログラムでは、token()を呼びだすことにより以下ようにtypeとvalue が返る。
- value 数値や変数に対応する値が入る大域変数
- last_token tokenの型が入る。token()は、この型を返す。
- 'v' ... 変数
- '0' ... 数値 (int)
- '*'など ... その他のtoken
例えば、 (2+1030/a)-2 という式は以下のように分解される。
宿題
Subject: Report on Compiler consturction Lecture 10/29
というSubjectのメールにして、kono@ie.u-ryukyu.ac.jp まで送ること。また授業を受けなかったものは、課題を、
Subject: Practice on Compiler consturction Lecture 10/29
というサブジェクトで送ること。