1. No category

6 コード生成
コンパイラの最終的な目的は，抽象構文木や中間表現から目的コードを生成することである．このような
目的コードの生成を，コード生成と呼び，コード生成を行うコンパイラの部分をコード生成器とよぶ．本節
では，コード生成に具体性をもたせるために， Linux 上の x86 コード（32 ビット）を例に，コード生成を解
説する．
6.1 コード生成の方針
□ 構成 ：
ソースプログラム
−→
字句解析器（Lexer）
コード生成器（Emitter）
□ 使用レジスタ
トークン
−→
構文解析器（Parser）
アセンブリコード（tmp.s）
−→
抽象構文木（Absyn）
−→
アセンブラとリンカ（gcc -m32）
実行コード（a.out）
−→
： レジスタ %eax と %ebx を値の保持に用いる． %ebp はフレームポインタ， %esp はス
タックポインタを表す．
□ 式の結果 ： スタックのトップに生成する．
□ スタックレイアウト
：実引数，局所変数，静的リンクは，%ebp を基準にアクセスする．
argument n
...
argument 1
12(%ebp)
static link
return address
%ebp
old %ebp
local variable
-4(%ebp)
...
%esp
previous result
pushl
popl
6.2 算術演算と代入
□ 加算 ： レジスタ（%eax）の値とスタックトップ（(%esp)）の値を加算し，結果をスタックトップに生
成する．
61
popl %eax
addl %eax, (%esp)
□ 減算 ： スタックトップ（(%esp)）の値からレジスタ（%eax）の値を減算し，結果をスタックトップに
生成する．
popl %eax
subl %eax, (%esp)
□ 積算 ： レジスタ（%eax）の値とスタックトップ（(%esp)）の値を積算し，結果をスタックトップに生
成する．imull は，結果を %edx:%eax に格納する．
popl %eax
imull (%esp), %eax
movl %eax, (%esp)
□ 除算 ：スタックトップ（(%esp)）の値をレジスタ（%eax）の値で割り，結果をスタックトップに生成す
る．idiv %ebx は，%edx:%eax を %ebx で除算し，%eax に商，%edx に剰余を格納する．
popl %eax
movl %eax, %ebx
popl %eax
movl $0, %edx (* the same as cdq *)
idivl %ebx
pushl %eax
□ 変数参照 ：offset に対応する変数の値をスタックに積む．
• 参照元の関数のフレーム内
movl -offset(%ebp), %eax
pushl %eax
• 異なる関数のフレーム内
movl %ebp, %eax
movl 8(%eax), %eax
← 入れ子の深さの差だけ並べる
...
movl -offset(%eax), %eax
pushl %eax
□ 代入 ：スタックトップ（(%esp)）の値を，offset に対応する変数に代入する．
• 参照元の関数のフレーム内
popl %eax
movl %eax, -offset(%ebp)
• 異なる関数のフレーム内
62
movl %ebp, %ebx
← 入れ子の深さの差だけ並べる
movl 8(%ebx), %ebx
...
movl %eax, -offset(%ebx)
6.3 関数
関数呼出し
：引数 argsSize 個（静的リンクを含む）の関数 f unc を呼ぶ．返戻値は，%eax で返す．
pushl arg n
...
pushl arg 1
静的リンクを渡すコード
call f unc
addl argsSize, %esp
pushl %eax
□ 静的リンクの渡し
：
• caller の入れ子の深さ ≥ callee の入れ子の深さ
movl %ebp, %ebx
movl 8(%ebx), %ebx
←
(入れ子の深さの差 + 1) だけ並べる
...
pushl %ebx
• caller の入れ子の深さ < callee の入れ子の深さ
pushl %ebp
関数の開始 ： %ebp をスタックに保存し，%esp の値を %ebp へ転送した後，必要な局所変数分 f rameSize
だけ %esp を減算する．f rameSize は局所変数のサイズに相当する．
pushl %ebp
movl %esp, %ebp
subl %f rameSize, %esp
関数からの戻り
：leave で %ebp と %esp を元に戻し（%ebp の値を %esp にコピーし，スタックトップの
値を %ebp にポップする）
，ret で呼出元の次のアドレスに戻る
leave
ret
6.4 文字列の定義と入出力
□ 文字列（string ）割付 ：
63
• 任意の文字列：アドレス label として扱う．
.data
label:
.string
"string"
.text
.align 4
• 整数の入出力用フォーマット文字列：共通のラベル IO を用いる．
IO:
.string "%d"
.text
.align 4
□ 入出力 ：
• スタックトップの印字：
pushl $label
call printf
addl $4, %esp
• スタックトップの整数を標準出力から出力：
pushl $IO
call printf
addl $8, %esp
• 標準入力から変数 x への入力：
pushl %ebp
subl $of f setOf x, (%esp)
pushl $IO
call scanf
addl $8, %esp
6.5 関係演算命令と分岐命令
9 章では，x86 の四則演算に必要な命令と出力の仕方について解説した．しかし，これだけでは，直線的な
プログラムしか記述することができない．そこで，入出力の方法を確認するとともに，x86 における分岐命令
を紹介しておこう．
□ label への無条件分岐
：
64
jmp label
□ 関係演算 ：
popl %eax
popl %ebx
cmpl %eax, %ebx
□ 条件分岐 ： 関係演算（C 言語風）に対する命令は次のとおり．
>
：jg label
<
：jl label
>= ：jge label
<= ：jle label
== ：je label
! = ：jne label
□ else がない if 文 ：if ( cond ) stmt
関係演算のオペランドの命令列
cmpl 命令
Li への条件分岐命令
stmt に対する命令列
Li:
□ else 付きの if 文 ：if ( cond ) stmt1 else stmt2
関係演算のオペランドの命令列
cmpl 命令
Li への条件分岐命令
stmt1 に対する命令列
Lj への無条件分岐
Li:
stmt2 に対する命令列
Lj:
ここで気を付けなければならないのは，条件分岐の部分である．条件分岐命令は，その条件が満たされ
る場合にラベルへのジャンプを行う．しかし，上で示した命令列パターンは，cond が満たされた場合
のコードが条件分岐のすぐ後にきている．これを実現するためには，cond における関係演算を反転さ
せた分岐命令を使わなければならない．各関係演算と変換後の条件分岐の関係を下に示す．
• >： <= に当たる jle
• <：>= に当たる jge
65
• >=：< に当たる jl
• <=：> に当たる jg
• ==：! = に当たる jne
• ! =：== に当たる je
次に while 文に対する変換は次のようになる．
□ while 文 ：while ( cond ) stmt
Li:
関係演算のオペランドの命令列
cmpl 命令
Lj への条件分岐命令
stmt に対する命令列
Li への無条件分岐命令
Lj:
if 文同様，条件分岐は，関係演算を反転させた条件をもつ分岐を用いる．
66