Compiler Construction Lecture 10/29

# 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 または、字句解析器という。

字句解析のルールは簡単で、

数字の続き
一文字の英字
その他の記号((+,-,*,/,>)

を認識すれば良い。ここでcommentも消してしまうのが良い。字句解析を表すのに、正規表現というのを使うこともできる。

[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

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

Compiler Construction Lecture 10/29

先週の復習
* これ がアセンブラの命令表である。
i386のアセンブラ
問題1
さらにgdbの使い方を追求する
アセンブラ(Assembler)を使った計算
問2
問2
Tokenizer 字句解析
手で木に変換する
* この
宿題

Shinji KONO / Mon Nov 26 17:20:50 2001