中間コード

コンパイラ資料
中間コード
160601a
ここまでの流れ
型検査
トークン
AST
字句解析
構文解析
属性
中間コード
レジスタ
割り付け
意味解析
Intermediate representation (IR)
ASTを抽象機械のアセンブリ言語に翻訳する
block
{
}
:=
decl
int x;
x:=x+3;
Mov r4 Loc(0)
Mov r5 r4
(x : int)
+
x
x
AST
Add r5 3
Mov r4 r5
3
IR
IRの特徴
• ＣＰＵを模した抽象機械の命令
– 一般的な命令（詳細はあとで）
– 一般的なデータアクセス（メモリ、レジスタ、即値）
– 特定のフレームレイアウト（7章）に依存しない
• データ構造のまま（まだ機械的な編集操作が可能）
• 汎用レジスタ無限個
IRの役割
• CPUにとってのAST
– マシン非依存（マシン依存コードへの中継地点）
• レジスタの割り当てのためのデータ構造
• 最適化のためのデータ構造（オペランドも）
– mov r5 r5
同一性検出⇒除去可能
本IR独自の設計方針
• x86アセンブリに近い（マシン独立でない）
– 命令選択(instruction selection)の処理をスキッ
プできる
• kittyの機能に必要なもののみに限定
– アドレス計算（配列,ポインタの脱参照に必要）は
しない
IR (とはいってもほぼx86/アセンブリ（INTEL記法）)
命令：
Mov a1 a2
Add a1 a2
Sub a1 a2
Mul a1
Div a1
Not a
Call fl
Label sl
Jmp sl
Cmp a1 a2
Je sl
Jne sl
オペランド: ()内はパラメータ
Imm(n) --- 即値n
Reg(n) --- n番目の汎用レジスタ
Formal(n) --- n番目の仮引数の場所
Arg(n) --- n番目の実引数の場所
Local(n)--- n番目の局所変数の場所
Save(n) --- レジスタ退避場所n番目
Formal, Arg,Localはメモリ(フレーム、後述)上の場所
ラベル
SimpleLabel(n)--- ジャンプ用ラベル
FunLabel(文字列) --- 関数名ラベル
a1, a2,aはオペランド flはFunLabel, slはSimpleLabel
即値へのmove、memoryからmemoryへのmoveは禁止
命令の意味
命令
# 意味
Mov a1 a2
# a2（の内容）をa1にコピー
Add a1 a2
# a1←a1+a2
Sub a1 a2
# a1←a1-a2
Mul a1
# eax ←eax ×a1 (edxを壊す)
Div a1
# eax←eax ÷a1 (edxを壊す)
Not a
#否定（bit反転）
Call funlabel
# ラベル funlabelをもつ関数を呼ぶ
Label simplelabel
# （ラベル）
Jmp simplelabel
#labelに飛ぶ
Cmp a1 a2
# a1とa2を比較（次と組で使う）→a1
Je simplelabel
#直前のCmpがa1=a2ならsimplelabelに飛ぶ
Jne simplelabel
#直前のCmpがa1!=a2ならsimplelabelに飛ぶ
Jg simplelabel
#直前のCmpがa1>a2ならsimplelabelに飛ぶ
｛Jge, Jl, Jle｝ # ｛>=,<,<=｝ (符号つき)
命令とオペランドのデータ構造
//instr.h
class Instr{
set<Reg*> use;
set<Reg*> def;
};
class Move_ : Instr{
Access* dst;
Access* src;
};
.....
class Access{/* 当面は空 */};
Label
class Imm : Access{
int value;
};
Move
class Reg : Access{
int sn;
int RA_temp;
};
Move
class Local : Access{
int pos;
};
Add
class SimpleLabel {
int sn;
};
Move
L2:
Mov r4 Loc(0)
Mov r5 r4
Add r5 3
Mov r4 r5
SimpleLabel 2
Reg 4
Reg 5
Local 0
Reg 4
Reg 5
Imm 3
Reg 4
Reg 5
翻訳に用いる変数・関数
• 命令列（コードリスト）記録用グローバル変数
list<Instr*>* code;
• 命令用コンストラクタ兼出力記録関数（icode）
void Move(Access* d,Access* s);
Move_(d,s)を作成してコードリスト末尾に追加
（ほかの命令も同様）
※ 大文字関数名はこの用途に用いることにする。
• Access、ラベルのコンストラクタ関数(小文字名)
Reg* reg(void),
Imm* imm(int n),
SimpleLabel* new_label(void),
FunLabel* fun_label(std::string) etc.
出力アセンブリコード仕様
アセンブリ言語：MASM (32bit)
ターゲットマシン：x86
実行環境,Windows
※ IRではまだコード出力はしない
MASMの構文：レジスタ
汎用レジスタ：
eax, ebx, ecx, edx, esi, edi
スタックポインタ： esp
ベースポインタ： ebp
ptrの指す番地のdsip個上は
DWORD PTR [ptr+disp]で参照
例
スタックに１ワード(32bit)積むとespは
WRD=32bit/1バイト=4だけ減る。
積む前のスタックの最上位要素を参照するには
[esp+4] とする
MASMの構文：ニーモニック
Op Arg1, Arg2
例 mov ebx, eax
意味：レジスタeaxの値をレジスタebxにコピー
例 mov DWORD PTR [ebx+n], eax
意味：レジスタeaxの値をebxの値をアドレスのn番
地上のメモリにコピー
例 mov eax, 5
意味：即値5をレジスタeaxにコピー
gas(AT&T記法)とMASM（microsoft asm, Intel記法）は
移動の向きとオペランドの順が逆なので注意
演算子ニーモニック
算術/2 add, sub 整数和、差
構文 add t, s
// t ← t ＋ s
構文 sub t, s
// t ← t － s
算術/1 imul, idiv 整数積、商
構文 imul t
// edx（上位）,eax ← t×eax
論理/2 and,or
ビットごとの論理積、和
比較/2 cmp
制御/1 jmp, je, jne
スタックからポップ pop t
スタックにプッシュ push s
アセンブリソースファイルの構成
.686P ; コメント: Pentium Pro以降
.XMM ; SIMD命令
.model flat ; メモリモデル（flat = 32bit/Windows）
EXTERN printf : PROC ; 外部記号宣言
_TEXT SEGHENT
hoge DB '%d', 0aH, 00H
_TEXT ENDS
PUBLIC _fact ;公開記号宣言
_TEXT SEGMENT
_fact PROC
push ebp
push ebp, esp
…..
ret
_fact ENDP
_TEXT ENDS
END
;定数定義（文字列）
Visual Studioでアセンブリを出力する
→
→
→
→
→
Projectのプロパティー
構成プロパティ
C/C++
出力ファイル
アセンブリの出力
（「なし」以外を選ぶ）
実験１
C/C++で次のコードをコンパイルして出力コードを観察せよ。
int main(){
int x=10;
x=x*x+7;
printf(“%d\n”x);
}
MASM Reference
• MASM Reference
http://msdn.microsoft.com/enus/library/afzk3475
• Directive Reference
http://msdn.microsoft.com/enus/library/8t163bt0%28v=vs.100%29.aspx
コマンドラインからMASMを使う
Visual Studio 2010 → Visual Studio Tools
Visual Studio コマンドプロンプトを起動
>ml [options] filelist [/link] linkoptions
例： ml factorial.asm msvcrt.lib
（factorial.asmをアセンブル後、オブジェクトを生成
してCランタイムライブラリmsvcrt.libとリンク）
コマンドラインスイッチのヘルプ：
>ml /? または ml /help
Visual Studio IDEからMASMを使う
プロジェクトのプロパティー → カスタムビルドツール → コマンドライン
[Release構成]
ml /c /Fo"$(Configuration)\$(ProjectName).obj" "$(ProjectName).asm"
[Debug構成]
ml /c /Zi /Fo"$(Configuration)\$(ProjectName).obj" "$(ProjectName).asm"
プロジェクトのプロパティー → カスタムビルドツール →出力ファイル
[すべての構成]
$(OutDir)$(ProjectName).obj
プロジェクトのプロパティー → リンカー → 入力→追加の依存ファイル
[すべての構成]
msvcrt.lib
【参考】 Visual Studioの設定で使用できる変数一覧：
http://msdn.microsoft.com/ja-jp/library/c02as0cs.aspx
実験２
• 実験１で生成したアセンブリファイルをアセン
ブル・リンクして実行結果を確かめよ
x86/32bit/MASMアセンブリ練習
• 10の階乗のプログラムをMASMで書け
– while文
– 再帰
IRへの翻訳の概略
• ASTノードごとに、生成すべき命令列をicode
で記述する。
– icodeはC++コードでIRを記述する、いわば言語
内言語
– icodeの命令の引数（Access*）はC++側で準備
する
– icode命令はアセンブリをその場で書く要領
• 値をもつASTノードは生成命令列が値を置く（
仮想）レジスタを返す。
レジスタは無限個
• 各ノードで計算の中間結果（値）は新しいレジ
スタに格納する。
reg() は呼ばれるたびに新しいシリアルナンバーを
もつレジスタを作って返す。（new_label()も同様に
新しいラベルを作って返す。）
• シリアルナンバー0～5(=REG_SIZE-1)の仮想
レジスタはあらかじめ実レジスタに割り当てて
おく
– 特定のレジスタを参照するために用いる
（precolored仮想レジスタ）
precolored の作成
翻訳のはじめにまとめて作成しておく
Reg*
Reg*
Reg*
Reg*
Reg*
Reg*
Eax=reg();
Ebx=reg();
Ecx=reg();
Edx=reg();
Esi=reg();
Edi=reg();
//r0
//r1
//r2
//r3
//r4
//r5
中間コード生成
IRVisitor : public Visitor{
ConditionIRVisitor* cv;//visitor切り替え用
void* visit(XXNode* n, void* obj);
// nを根とする木をIRに翻訳(条件式は除く）
// 式の木の場合は値を格納する場所(Access*)を返す。
}
ConditionIRVisitor : public IRVisitor{
IRVisitor* ev; //visitor切り替え用
void* visit(XXNode* n, SimpleLabel* label);
//条件式専用visitor：
//値が偽のときlabelにジャンプするIRに翻訳
}
void* IRVisitor::visit(OpNode* n, void* obj)
{
Access *t1,*t2;
Reg* rand;
t1=static_cast<Access*>(n->children[0]->accept(this,obj));
//第１被演算数を計算するコードを生成し、結果がおかれる場所をt1に代入する
t2=static_cast<Access*>(n->children[1]->accept(this,obj));
//第２被演算数を計算するコードを生成し、結果がおかれる場所をt2に代入する
switch(n->op_kind){
case PLUS_OP:
rand=reg();
//新しいレジスタをつくりrandに代入
Move(rand, t1);
//Move命令 rand ← t1 を生成
Add(rand,t2);
//Add命令 rand ← rand + t2 を生成
break;
.....
}
return rand;
}
void* IRVisitor::visit(IfNode* n, void* obj)
{
SimpleLabel* L1=new_label(); //ラベルL1を作る（まだ置かない）
SimpleLabel* L2=new_label(); //別のラベルL2を作る
n->children[0]->accept(this->cv,L1);//visitor切り替え
// 「条件式の値がfalseならL1にjumpするコード」を生成
n->children[1]->accept(this,obj); //if文のTrue部のコードを生成
Jmp(L2);
//「ラベルL2にjumpする命令」を生成
Label(L1);
//「ラベルL1」をここ（現時点のコード末尾）に貼る
n->children[2]->accept(this,obj); //if文のFalse部のコードを生成
Label(L2);
return nullptr;
}
//「ラベルL2」をここに貼る
void* IRVisitor::visit(RelNode* n,
void* ob)
{
Acccess *t1,*t2;
t1=static_cast<Access*>
(n->children[0]->accept(this,ob));
t2=static_cast<Access*>
(n->children[1]->accept(this,ob));
Reg* rand=reg();
Move(rand,t1);
Rel(n->rel_kind, rand , t2);
return rand
}
Access* Rel(int kind, Access* left,
Access* right){
SimpleLabel *L1,*L2;
Cmp(left,right);
L1=new_label();
L2=new_label();
switch(kind){
case EQ:
Je(L1);
Move(left, imm(0));
Jmp(L2);
Label(L1);
Move(left, imm(~0));
Label(L2);
break;
...
}
return left;
}
void* ConditionIRVisitor::visit(RelNode*n,
void* Lf)
{
Acccess *t1,*t2;
t1=static_cast<Access*>
(n->children[0]->accept(this,nullptr));
t2=static_cast<Access*>
(n->children[1]->accept(this,nullptr));
Reg* rand=reg();
Move(rand, t1);
cRel(n->rel_kind, rand, t2,
static_cast<SimpleLabel*>(Lf));
return nullptr;
}
void cRel(int kind, Access* left,
Access* right, Access* Lf){
Cmp(left,right);
switch(kind){
case EQ:
Jne(Lf);
break;
...
}
}
課題 IR_visitor
関数呼び出しとリターン文を除くstatement
をIRに翻訳するプログラム
入力例
{
int x,s;
x := 100;
s := 0;
while (x <> 0) {
s := s+x;
x := x-1;
}
}
印字プログラムを（Vsitorパターンで）作
成して確かめよ。
印字例
Mov r6, 100
Mov Loc(1), r6
Mov r7, 0
Mov Loc(0), r7
L_1 :
Mov r8, Loc(1)
Cmp r8, 0
Je L_2
Mov r9, Loc(0)
Add r9, Loc(1)
Mov r10, r9
Mov Loc(0), r10
Mov r11, Loc(1)
Sub r11, 1
Mov r12, r11
Mov Loc(1), r12
Jmp L_1
L_2 :
参考(GNU assembler, gas)
コンパイルから実行ファイルまで
gccの場合
1. cc (gcc): Cを gasに翻訳(コンパイル)
foo.c  foo.s
as (Gnu Assembler, gas) ：gas を再配置可能オブジ
ェクトに変換（アセンブル）
foo.s  foo.o
ld : リンカ（または、リンクエディタ）
複数のオブジェクトを結合して、実行可能形式に。
foo.o  foo.exe
調査課題
cc -S filename.c はアセンブリコードのみを生成する. いろいろなC
言語ソースファイルで試し, 出力コードを調べよ.
cc -v filename.c はgccがどのような外部プログラムを呼び出して
いるかを表示する. 試せ.
cc -v filename.c >& hoge.sh でhoge.shに格納して編集し, アセン
ブリコードfilename.sをもとに実行可能ファイルを作成するシェ
ルスクリプトをつくれ. 引数, スイッチを削除してみてどれが必須
かしらべよ.
シェルスクリプト：
1行めに #!/usr/bin/sh と書いておけば以下の行がshから実行され
る. シェルスクリプトの引数は$1で参照できる. （ファイル名など）
出力アセンブリコード仕様
アセンブリ言語：gas (32bit)
ターゲットマシン：x86
実行環境,OS: Linux, Cygwin※など（POSIX）
※CygwinはPOSIXのみエミュレートするのでシステム
コールはない
gasの構文：レジスタ
汎用レジスタ：
%eax, %ebx, %ecx, %edx, %esi, %edi
スタックポインタ： %esp
ベースポインタ： %ebp
ptrの指す番地のdsip個上はdisp(ptr)で参照
例
スタックに１ワード(32bit)積むと%espは
WRD=32bit/1バイト=4だけ減る。
積む前のスタックの最上位要素を参照するに
は 4(%esp) とする
gasの構文：ニーモニック
Op Arg1, Arg2
例 movl %eax, %ebx
意味：レジスタ%eaxの値をレジスタ%ebxにコピー
例 movl %eax, n(%ebx)
意味：レジスタ%eaxの値を%ebxの値をアドレスの
n番地上のメモリにコピー
例 movl $5, %eax
意味：即値5をレジスタ%eaxにコピー
gas(AT&T記法)とmasm（microsoft asm, Intel記法）は
移動の向きとオペランドの順が逆なので注意
演算子ニーモニック
算術/2 addl, subl 整数和、差
構文 addl s, t
// t ＋ s → t
構文 subl s, t
// t － s → t
算術/1 imul, idiv 整数積、商
構文 imul t
// t×%eax →%edx（上位）,%eax
論理/2 and,or
ビットごとの論理積、和
比較/2 cmp
制御/1 jmp, je, jne
スタックからポップ popl t
スタックにプッシュ pushl s
x86/32bit/gasアセンブリ練習
Cで次のコードをコンパイル（cc -S）して出力コードを観察せよ。
int main(){
int x=10;
x=x*x+7;
printf(“%d\n”,x);
}
• 10の階乗のプログラムをgasで書け
– while文
– 再帰

Download Report