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

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

中間語（続き） 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] 機械語

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

木のパターンマッチングによる コード生成 = → 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は定数にマッチする。

= + * a r1 2 ↑ + b r1

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

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

= + 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)

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

ダイナミックプログラミングによる コード生成 (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

(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

(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

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

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

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

= + 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

= + 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

= 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

= 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

= 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 ↑

= 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

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

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

文のコード生成 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

文のコード生成 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:

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

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