コンパイラ資料 中間コード 160601a.

Presentation on theme: "コンパイラ資料 中間コード 160601a."— Presentation transcript:

1 コンパイラ資料 中間コード 160601a

2 ここまでの流れ 意味解析 型検査 トークン 字句解析 構文解析 AST 属性 中間コード レジスタ 割り付け

3 Intermediate representation (IR)
ASTを抽象機械のアセンブリ言語に翻訳する block Mov r4 Loc(0) Mov r5 r4 Add r5 3 Mov r4 r5 := decl { int x; x:=x+3; } (x : int) + x x 3 AST IR

4 IRの特徴 ＣＰＵを模した抽象機械の命令 データ構造のまま（まだ機械的な編集操作が可能） 汎用レジスタ無限個 一般的な命令 （詳細はあとで）
一般的な命令　（詳細はあとで） 一般的なデータアクセス（メモリ、レジスタ、即値） 特定のフレームレイアウト（7章）に依存しない データ構造のまま（まだ機械的な編集操作が可能） 汎用レジスタ無限個

5 IRの役割 CPUにとってのAST レジスタの割り当てのためのデータ構造 最適化のためのデータ構造（オペランドも）
マシン非依存（マシン依存コードへの中継地点） レジスタの割り当てのためのデータ構造 最適化のためのデータ構造（オペランドも） mov r5 r5 同一性検出⇒除去可能

6 本IR独自の設計方針 x86アセンブリに近い（マシン独立でない） kittyの機能に必要なもののみに限定
命令選択(instruction selection)の処理をスキップできる kittyの機能に必要なもののみに限定 アドレス計算（配列,ポインタの脱参照に必要）はしない

7 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は禁止

8 命令の意味 命令 # 意味 Mov a1 a2 # a2（の内容）をa1にコピー Add a1 a2 # a1←a1+a2
命令 #　意味 Mov a1 a 　# a2（の内容）をa1にコピー Add a1 a2 　　　　# a1←a1+a2 Sub a1 a # a1←a1-a2 Mul a # 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｝　　# ｛>=,<,<=｝ (符号つき) ....

9 命令とオペランドのデータ構造 Label SimpleLabel 2 Move Reg 4 Local 0 Reg 4 Move Reg 5
//instr.h class Instr{ set<Reg*> use; set<Reg*> def; }; class Move_ : Instr{ Access* dst; Access* src; ..... class Access{/* 当面は空 */}; class Imm : Access{ int value; class Reg : Access{ int sn; int RA_temp; class Local : Access{ int pos; class SimpleLabel { L2: Mov r4 Loc(0) Mov r5 r4 Add r5 3 Mov r4 r5 Label SimpleLabel 2 Move Reg 4 Local 0 Reg 4 Move Reg 5 Add Reg 5 Imm 3 Move Reg 4 Reg 5

10 翻訳に用いる変数・関数 命令列（コードリスト）記録用グローバル変数 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.

11 出力アセンブリコード仕様 アセンブリ言語：MASM (32bit) ターゲットマシン：x86 実行環境,Windows
※　IRではまだコード出力はしない

12 MASMの構文：レジスタ 汎用レジスタ： eax, ebx, ecx, edx, esi, edi スタックポインタ： esp
ベースポインタ：　ebp ptrの指す番地のdsip個上は DWORD PTR [ptr+disp]で参照 例　 スタックに１ワード(32bit)積むとespは WRD=32bit/1バイト=4だけ減る。 積む前のスタックの最上位要素を参照するには [esp+4] とする　

13 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記法）は 移動の向きとオペランドの順が逆なので注意

14 演算子ニーモニック 算術/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

15 アセンブリソースファイルの構成 .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 END

16 Visual Studioでアセンブリを出力する
Projectのプロパティー → 構成プロパティ → C/C++ → 出力ファイル → アセンブリの出力 → （「なし」以外を選ぶ）

17 実験１ C/C++で次のコードをコンパイルして出力コードを観察せよ。 int main(){ int x=10; x=x*x+7;
printf(“%d\n”x); }

18 MASM Reference MASM Reference Directive Reference
Directive Reference

19 コマンドラインから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

20 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の設定で使用できる変数一覧：

21 実験２ 実験１で生成したアセンブリファイルをアセンブル・リンクして実行結果を確かめよ

22 x86/32bit/MASMアセンブリ練習 10の階乗のプログラムをMASMで書け while文 再帰

23 IRへの翻訳の概略 ASTノードごとに、生成すべき命令列をicodeで記述する。
icodeはC++コードでIRを記述する、いわば言語内言語 icodeの命令の引数（Access*）はC++側で準備する icode命令はアセンブリをその場で書く要領 値をもつASTノードは生成命令列が値を置く（仮想）レジスタを返す。

24 レジスタは無限個 各ノードで計算の中間結果（値）は新しいレジスタに格納する。
reg()　は呼ばれるたびに新しいシリアルナンバーをもつレジスタを作って返す。 （new_label()も同様に新しいラベルを作って返す。） シリアルナンバー0～5(=REG_SIZE-1)の仮想レジスタはあらかじめ実レジスタに割り当てておく 特定のレジスタを参照するために用いる（precolored仮想レジスタ）

25 precolored の作成 翻訳のはじめにまとめて作成しておく Reg* Eax=reg(); //r0
Reg* Ebx=reg(); //r1 Reg* Ecx=reg(); //r2 Reg* Edx=reg(); //r3 Reg* Esi=reg(); //r4 Reg* Edi=reg(); //r5

26 中間コード生成 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に翻訳

27 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;

28 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); //「ラベルL2」をここに貼る return nullptr; }

29 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; ...

30 課題 IR_visitor 印字例 関数呼び出しとリターン文を除くstatementをIRに翻訳するプログラム 入力例 { int x,s;
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 : 関数呼び出しとリターン文を除くstatementをIRに翻訳するプログラム 入力例 { int x,s; x := 100; s := 0; while (x <> 0) { s := s+x; x := x-1; } 印字プログラムを（Vsitorパターンで）作成して確かめよ。

31 参考(GNU assembler, gas)

32 コンパイルから実行ファイルまで gccの場合 cc (gcc): Cを gasに翻訳(コンパイル) foo.c  foo.s
as (Gnu Assembler, gas) ：gas を再配置可能オブジェクトに変換（アセンブル） 　　　foo.s  foo.o ld : リンカ（または、リンクエディタ） 　　複数のオブジェクトを結合して、実行可能形式に。 　　foo.o  foo.exe

33 調査課題 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で参照できる. （ファイル名など）

34 出力アセンブリコード仕様 アセンブリ言語：gas (32bit) ターゲットマシン：x86
実行環境,OS:　Linux, Cygwin※など（POSIX） ※CygwinはPOSIXのみエミュレートするのでシステムコールはない

35 gasの構文：レジスタ 汎用レジスタ： %eax, %ebx, %ecx, %edx, %esi, %edi スタックポインタ： %esp
ベースポインタ：　%ebp ptrの指す番地のdsip個上はdisp(ptr)で参照 例　 スタックに１ワード(32bit)積むと%espは WRD=32bit/1バイト=4だけ減る。 積む前のスタックの最上位要素を参照するには 4(%esp) とする　

36 gasの構文：ニーモニック Op Arg1, Arg2 例 movl %eax, %ebx
例　movl %eax, n(%ebx) 意味：レジスタ%eaxの値を%ebxの値をアドレスのn番地上のメモリにコピー 例　movl $5, %eax 意味：即値5をレジスタ%eaxにコピー gas(AT&T記法)とmasm（microsoft asm, Intel記法）は 移動の向きとオペランドの順が逆なので注意

37 演算子ニーモニック 算術/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

38 x86/32bit/gasアセンブリ練習 10の階乗のプログラムをgasで書け while文 再帰
Cで次のコードをコンパイル（cc -S）して出力コードを観察せよ。 int main(){ int x=10; x=x*x+7; printf(“%d\n”,x); } 10の階乗のプログラムをgasで書け while文 再帰