アルゴリズムとデータ構造1

コンパイラ
2012年10月25日
酒居敬一@A468([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
中間表現
前回までの内容


字句解析

ソースプログラムという文字の並びから、字句の並びへ変換。


ただし、字句は構造を持ったデータ。つまり少し抽象化したデータの並び。
構文解析

字句の並びから、構造を持ったデータの集まりへ変換。


名前やデータ構造は名前表に出力する。
では、制御構造(文の構造)はどうする???

とりあえずは、構文木や4つ組として出力する、と説明した。とりあえず...
今回の内容


構文木や4つ組みとして表されるものをきちんと説明。
次回の内容


2
意味解析
二分木
二項演算や代入は二分木で表現可能。



後順走査することで、後置記法のオブジェクトコードを生成可能。
演算・代入は子を2つもつノード。


変数や定数はリーフ。


ノードは、その結果を親ノードへ返す。
参照した値を親ノードへ返す。右辺値を返す?
代入ノードの左の子


親ノードが代入ノードである場合を判断し、左辺値を返す。
右辺値を返し、代入ノードでその右辺値の指す先に値を置く。
関数呼び出しは特殊ノードとして表現する。


引数の数だけ子を持つノード。

3
戻り値を親ノードへ返す。
式y+find_max(a+b, c, 0)/(x-1)の構文木
〈式〉ノードの種類
(call,+,-,*,/,>,>=,<,<=,<>,=)
子ノードへのポインタ1
子ノードへのポインタ2
型
語長
+
y
/
call
find_max
arg_vector
+
a
x
0
b
c
1
〈リーフ〉ノードの種類
(名前(変数, 関数), 定数)
名前表へのインデックス
定数値
※ この例では代入や左辺値を必要とする演算は表されていない。
4
左辺値と右辺値
左辺値(l-value)



代入の左辺に置けるもの。代入先に指定できるもの。
言語によるが、たいていは変数。

実行環境が許せば、*((int *)0x1000) でも左辺値になる。
右辺値(r-value)



代入の右辺に置けるもの。
左辺値になれなくても、右辺値になるものはある。


C言語における、関数名・配列名は左辺値にはなれない。
式の返す値。 x++は、右辺値にしかなれない。++(x++)はエラー。
*p = 10; と書けるとき、*p が代入の左辺値である。
pが左辺値かどうかは、pの定義しだい。
pが*演算子で参照された結果が左辺値だ、というだけ。

5
四つ組
木として保持するより小さく、外部ファイルに出しやすい。


保持する情報は木と変わらない。
つぎの情報をひとつの四つ組として持つ

1.
2.
3.
4.
演算子の情報
第一オペランドの情報
第二オペランドの情報
演算結果の保存先
保存先にコンパイラが生成した一時的な変数も存在する。


6
木の場合には、演算ノードが保持している、ということに対応。
四つ組と木構造
=
四つ組
(①*,②c,③d,④tmp#1)
(①+,②b,③tmp#1,④tmp#2)
(①=,②tmp#2,③,④@a)
a
+
b
*
四つ組の代入形式表現
tmp#1 := c*d
tmp#2 := b+tmp#1
a := tmp#2
代入のときの保存先は左辺値である。
四つ組で@をつけているところで、アドレスで参照している。
一方の木構造の例では、名前で参照している。
7
c
d
四つ組と木構造の関係
木を後順走査した結果と四つ組表現がよく合う。



子を先に走査することがオペランドを用意することに対応し、
演算子はそれらオペランドに作用することから後で出力する。
演算途中の値は、一時変数に置く。
変数や定数


木でも四つ組でも名前表に置き、インデックスなどで参照する。
木は必ずしも2分木である必要はない。



三項演算子・引数が2個より多い関数は多分木のほうがよい。
if-then-elseやforのような制御構造を表す場合も多分木
のほうがよく合う。
四つ組は書き方が機械命令に近い。


8
除算のように、戻り値が2つ以上ある演算も書けたりする。
z=y+1/(x-1)の木構造と四つ組
対応する四つ組
①(-,x,1,tmp#1)
②(/,1,tmp#1,tmp#2)
③(+,y,tmp#2,tmp#3)
④(=,tmp#3,,@z)
=
+
z
対応する三つ組
/
y
-
1
x
9
①(-,x,1)
②(/,1,①)
③(+,y,②)
④(=,③,@z)
1
代入形式
①tmp#1 := x-1
②tmp#2 := 1/tmp#1
③tmp#3 := y+tmp#2
④z := tmp#3
中間言語の必要性

四つ組は3オペランド形式の機械語に近いとはいうものの…

命令セットアーキテクチャは、マイクロアーキテクチャの影響
を受けて設計されるため、そのままでは使いにくい。

オペランドの組み合わせに関する直交性が限定的。


一時変数としてのレジスタ数に限りがある。


SPARC v9で32個、IA-32で8個、だけど使途に制約あり。
即値・絶対アドレスといった値の大きさに制約がある。


メモリ対メモリの演算ができない命令セットアーキテクチャが多い。
たいていは倍精度浮動小数点数を即値で表せない。
レジスタの使途に制約がある場合がある。

10
整数演算用・浮動小数点演算用・アドレス保持用・暗黙的使用など。
例: IA-32とH8(単純なもの)

IA-32(Intel表記)
11

H8(gas表記)
add
add
lea
lea
eax,ebx
[eax],ecx
eax,[ebx+edx]
eax,[esi+edi*4+8]
add
r0,r1
mul
eax,edx
mulxu
r0l,r1
mov
mov
mov
mov
ecx,eax
eax,[ebx+16]
eax,[ebx+ecx*4]
[edx],ecx
mov
mov
r2,r5
@(12,r2),r0
mov
r0,@r1
例:dsPIC33Fのmac命令(複雑なもの)

Multiply and Accumulate命令
mac
W4*W5,A, [W8],W6, [W10],W7, [W13]
W4とW5の乗算結果をAアキュムレータへ加算(積和)
W8で指し示されるXメモリからW6へロード(次命令のためのプリロード)
W10で指し示されるYメモリからW7へロード(次命令のためのプリロード)
W13で指し示すメモリへBアキュムレータの値を飽和・丸めの後でストア

先行命令の結果のストア、現在命令の演算、後続命令の
オペランドのロード、を同時に1クロック時間で片付ける。

構文解析後に、いきなり生成することはできません!
12
ポインタや参照といったもの

C言語は、高級アセンブリ言語Cと言い換えても
構わないくらい、機械語とつながりが深い。
int *f();
int (*f)();
/* fはintへのポインタを返す関数 */
/* fはintを返す関数へのポインタ */
char **argv;
/* charへのポインタのポインタ */
int (*daytab)[13]; /* daytabはintを要素とする要素数13の配列へのポインタ */
int *daytab[13];
/* daytabはintへのポインタを要素とする要素数13の配列 */
char (*(*x())[])(); /* xはcharを返す関数へのポインタの配列へのポインタを返す関数 */
char (*(*x[3])())[5];/* xはcharを要素とする要素数5の配列へのポインタを返す関数
へのポインタを要素とする要素数3の配列 */
出典: "プログラミング言語C 第2版", 共立出版, 149ページ, 2001年.
13
例:char (*(*x[3])())[5];という定義
x
例の定義ではポインタ3個分の大きさのメモリがxとして定義されます(xは名前による参照)。
ポインタの大きさは処理系依存ですが、大きさはintと同じことが多い。
xの要素を参照する、つまりプログラムの中で y = x[0](); としたときのyは?
x:
y:
.word
.word
mov
jsr
@x,r0
@r0
a, b, c
0
! a, b, cは関数のエントリーポイントであるとする。
! 戻り値を入れる場所とする。yの型はchar (*)[5]
! x[0]()に対応し、呼ばれた関数がr0に値を返す。
y
yには関数から戻ったときのr0の値が入る。その変数の指す先に要素数5のcharの配列がある。
14
関数呼び出しの()と、キャストの()

下線をつけたところが関数呼び出しの()。


char (*(*x[3])())[5];
文脈で区別され、内側から読むと、「xは大きさ3の配列で、
その要素を参照することで関数が呼び出され、呼び出された
関数の返す値を参照すると大きさ5のchar配列にたどり着く。」
関数呼び出しのときの()の左側のオブジェクトは何?
エントリーポイントを保持する変数。関数へのポインタ。
1.
ポインタを参照して得た値が関数へのエントリーポイント
ポインタ変数は関数ではないが、感覚的に同じように使える。


アセンブリ言語レベルでは、ラベルでしかないもの。
2.

ラベルは最終的にはldによりアドレスに変換されます。


15
感覚的には名前=関数。
左辺値