目的コードの生成 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第９章.

Presentation on theme: "目的コードの生成 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第９章."— Presentation transcript:

1 目的コードの生成 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第９章

2 中間語 構文木とDAG 四つ組（３番地コード）と三つ組 抽象構文木（AST：abstract syntax tree）
DAG（directed acyclic graph） 中間木 四つ組（３番地コード）と三つ組 （演算子, オペランド１, オペランド２, 結果） （演算子, オペランド１, オペランド２） 結果を三つ組の場所で示す。

3 中間語（続き） RTL 機械語 Register transfer language 命令語はレジスタとのやりとりが主。
例：　a[i]=b+1; r[1]=m[b] r[1]=r[1]+1 r[2]=m[i] r[2]=r[2]*4 m[a+r[2]]=r[1] 機械語

4 コード生成器生成系 パターンマッチングによるコード生成器 コード生成器 目的コード 中間木 パターン 機械語 ….. ….. +
→ add reg, reg, const add r1, r1, 4 + reg const ….. ….. r1 4 パターンマッチングと コード生成のプログラム

5 木のパターンマッチングによる コード生成 = → R2 → R2 * + R2 + 2 R1 C R1 C R1
↑ → R2 → R2 * + R2 + 2 R1 C R1 C R1 store R2,C(R1) load R2,C(R1) shiftL R2,R1,1 R1やR2はレジスタにマッチする。 Cは定数にマッチする。

6 = + * a r1 2 ↑ + b r1

7 = + r2 * a r1 2 ↑ + b r1 store r2,a(r1)

8 = + r2 * a r1 2 r2 ↑ + shiftL r2,r2,1 b r1 store r2,a(r1)

9 = + r2 * a r1 2 r2 + load r2,b(r1) shiftL r2,r2,1 b r1 store r2,a(r1)
↑ + load r2,b(r1) shiftL r2,r2,1 b r1 store r2,a(r1)

10 極大食い（maximal munch） トップダウンのパターンマッチング いろいろなマッチングがありうるときは、
中間木の根から葉の方向に。 いろいろなマッチングがありうるときは、 できるだけ大きなパターンを選ぶ。 極大食いが常に最適とは限らない。

11 ダイナミックプログラミングによる コード生成
(1) (2) (3) C → R1 = = + R2 R1 ↑ C R1 R2 M[R1+C]←R2 M[R1]←M[R2] R1←C cost=5 cost=6 cost=1

12 (5) (4) (6) → R1 → R2 → R1 + C + C R1 C R1 R1←M[C] R2←M[R1+C] R1←R1+C
↑ → R1 → R2 ↑ → R1 + C + C R1 C R1 R1←M[C] R2←M[R1+C] R1←R1+C cost=3 cost=5 cost=1

13 (7) → R1 + (8) R2 → R2 + + R1 R2 C R1 R1←R2+M[R1+C] R1←R1+R2 cost=6
↑ R2 → R2 + + R1 R2 C R1 R1←R2+M[R1+C] R1←R1+R2 cost=6 cost=1

14 = + ↑ a ↑ + k b ↑ j a[k]=b[j];

15 = + ↑ a ↑ + k b ↑ r1←b; 1 b; 0 j

16 = + a + r3←a; 1 a; 0 b k r1←b; 1 r4←k; 1 b; 0 k; 0 j r2←j; 1 j; 0 ↑ ↑

17 = + a + r3←a; 1 a; 0 r2←M[j]; 0+3=3 b r2←M[r2+0]; 1+5=6 k r1←b; 1
↑ a ↑ + r3←a; 1 a; 0 r2←M[j]; 0+3=3 r2←M[r2+0]; 1+5=6 k b ↑ r1←b; 1 b; 0 r4←k; 1 k; 0 j r2←j; 1 j; 0

18 = + r2←r2+b; 3+0+1=4 a + r2←r2+r1; 3+1+1=5 r3←a; 1 a; 0 r2←M[j]; 0+3=3
↑ r2←r2+b; 3+0+1=4 r2←r2+r1; 3+1+1=5 a ↑ + r3←a; 1 a; 0 r2←M[j]; 0+3=3 r2←M[r2+0]; 1+5=6 k b ↑ r1←b; 1 b; 0 r4←k; 1 k; 0 j r2←j; 1 j; 0

19 = r2←M[r2+b]; 3+0+5=8 r2←M[r2+0]; 4+5=9 + r2←r2+b; 3+0+1=4 a +
↑ r2←r2+b; 3+0+1=4 r2←r2+r1; 3+1+1=5 a ↑ + r3←a; 1 a; 0 r2←M[j]; 0+3=3 r2←M[r2+0]; 1+5=6 k b ↑ r1←b; 1 b; 0 r4←k; 1 k; 0 j r2←j; 1 j; 0

20 = r2←M[r2+b]; 3+0+5=8 r2←M[r2+0]; 4+5=9 + a + r2←M[j]; 0+3=3 b k
↑ a ↑ + r2←M[j]; 0+3=3 k b ↑ r1←b; 1 b; 0 j

21 = r2←M[r2+b]; 3+0+5=8 r2←M[r2+0]; 4+5=9 + r2←r2+b; 3+0+1=4 a + b k j ↑

22 = r4←r4+a; 3+0+1=4 r4←r4+r3; 3+1+1=5 r2←M[r2+b]; 3+0+5=8
↑ r4←M[k]; 0+3=3 r4←M[r4+0]; 1+5=6 r2←r2+b; 3+0+1=4 r2←r2+r1; 3+1+1=5 a ↑ + r3←a; 1 a; 0 r2←M[j]; 0+3=3 r2←M[r2+0]; 1+5=6 k b ↑ r1←b; 1 b; 0 r4←k; 1 k; 0 j r2←j; 1 j; 0

23 M[r4+a]←r2; 3+8+5=16 M[r4]←M[r2]; 4+4+6=14 = r4←r4+a; 3+0+1=4
r2←M[r2+b]; 3+0+5=8 r2←M[r2+0]; 4+5=9 + ↑ r4←M[k]; 0+3=3 r4←M[r4+0]; 1+5=6 r2←r2+b; 3+0+1=4 r2←r2+r1; 3+1+1=5 a ↑ + r3←a; 1 a; 0 r2←M[j]; 0+3=3 r2←M[r2+0]; 1+5=6 k b ↑ r1←b; 1 b; 0 r3←k; 1 k; 0 j r2←j; 1 j; 0

24 r2 ← M[j] 3 r2 ← r2+b 1 r4 ← M[k] 3 r4 ← r4+a 1 M[r4] ← M[r2] 6

25 文のコード生成 c=true c=false e=e1|e2 e=e1&e2 e=!e1 e=変数 Load R,e
T(e,c,L)の定義：if (e==c) goto Lの目的コード c=true c=false e=e1|e2 T(e1,true,L) T(e2,true,L) T(e1,true,newL) T(e2,false,L) newL: e=e1&e2 T(e1,false,newL) T(e1,false,L) e=!e1 e=変数 Load R,e BrT R,L BrF R,L

26 文のコード生成 T((a&b)|!(c|d),true,L) = T(a&b,true,L)
= T(a,false,L1) Load R1,a BrF R1,L1 T(b,true,L) Load R1,b BrT R1,L L1: L1: T(!(c|d),true,L) =T(c|d,false,L) = T(c,true,L2) Load R1,c BrT R1,L2 T(d,false,L) Load R1,d BrF R1,L L2: L2:

27 手続き呼び出しのコード レジスタの使い方 特定目的に使われるレジスタ BrLink L ! Branch and Link
大域的に使われるレジスタ群 手続き呼び出しをしても値が変わらない。 呼び出され側で大域的なレジスタを使う場合は、 呼び出され側で退避する（callee save register）。 局所的に使われるレジスタ群 それが保証されないもの。 呼び出し側で局所的なレジスタを使っている場合は、 呼び出し側で退避する（caller save register）。

28 プロローグ エピローグ 呼び出し側 呼び出され側 L: フレーム領域の獲得 大域レジスタの退避 （特定レジスタの退避 と新設定も含む）
　と新設定も含む） 局所レジスタの退避 パラメタのセット 手続き本体のコード BrLink L 局所レジスタの回復 大域レジスタの回復 エピローグ フレーム領域の解放 戻り値のセット 戻り命令 呼び出し側 呼び出され側