プログラマから見えるCPU 一番下のレベルでコンピュータ上のプログラムがど のように表現されているかを理解する プログラムがどう表現されているか プログラムはコンピュータのメモリ上に載っている コンピュータのメモリには数字しか格納できない したがってプログラムは数字である どう表現されているのか 数

計算機学

プログラマから見える

CPU

●

一番下のレベルでコンピュータ上のプログラムがど

のように表現されているかを理解する

●

プログラムがどう表現されているか

– _{プログラムはコンピュータのメモリ上に載っている} – _{コンピュータのメモリには数字しか格納できない} – _{したがってプログラムは数字である} ●

どう表現されているのか？

– _{数字で表現された「命令」：機械語} – _{CPUごとに異なる}

コンピュータの構成

CPU レジスタ ALU メモリ I/O 周辺機器 キャッシュ バス

コンピュータの構成

●

CPU

– _{計算やデータ転送、制} 御などを司る ●

ALU

– _{データの算術演算・論} 理演算を行う ●

レジスタ

– _{演算・データ転送のた} めの数値の一時保存場 所 ●

キャッシュ

– _{メモリとのデータ転送を} 高速化 ●

メモリ

– _{データの記憶領域} – _{アドレス（番地）で管理} ●

バス

– _{データを転送する経路} ●

I/O

– _{周辺機器との入出力イ}

CPUアーキテクチャ

●

CPUの設計方針及びインタフェースの総称

– _{命令セットアーキテクチャ} ● アドレス空間、データの処理単位の長さ ● 「命令」の種類、機械語と命令の対応 ● レジスタの数や種類 – _{マイクロアーキテクチャ} ● レジスタや演算器（ALU）の論理構成 ● キャッシュの構成や容量 – _{システムアーキテクチャ} ● 各部の実装方式

CPUアーキテクチャの種類

●

CISC (Complex Instruction Set Computer)

– _{1命令が複雑で高度な動作をする}

– _{回路は複雑、命令あたりの動作は遅い} – _{x86系CPUなど}

●

RISC (Reduced Instruction Set Computer)

– _{1命令は単純な動作}

– _{回路は単純、命令あたりの動作は速い} – _{ARM, MIPSなど}

モデル

CPU

●

COMET-II （情報処理技術者試験用CPU)

– _{命令記述言語はCASL-IIと呼ばれる} – _{16bit CPU (16bit/word)}

– _{アドレス空間 64kword (128kbyte)} – _{レジスタ構成} ● 8個の汎用レジスタ(GR) ● プログラムレジスタ(PR) ● スタックポインタ(SP) ● フラグ(FR) GR0 (16) GR1 (16) GR2 (16) GR3 (16) GR4 (16) GR5 (16) GR6 (16) SP (16) PR (16) FR (3)

CPUの動作

1.プログラムレジスタ

_{(PR)に格納された数値をアドレ}

スとみなし、そのアドレスのメモリに格納された数

値を取り出す

2.プログラムレジスタの値を１増やす

3.取り出した数値を「命令」とみなし、解読

4.解読した内容に応じた動作を行う

5.1に戻る

命令セット

●

データ転送命令

●

算術演算・論理演算命令

●

比較演算命令

●

シフト演算命令

●

分岐命令

●

スタック操作命令

●

サブルーチン命令

●

その他

命令の形式

●

命令　

[オペランド]

– _{例： LD GR1,#FF00,GR2} – _{例： JNZ #001E} ●

オペランド（操作対象）の形式

– _{対象レジスタ1個 POP GR1} – _{対象レジスタ2個 LD GR1, GR2} – _{数値（アドレス） JUMP #FF00} – _{数値とレジスタ LAD GR0, 120} – _{数値とレジスタ2個 ST GR0, #FF00, GR1}

アドレッシングモード

●

例：

LD GRx, 対象

– _{対象の内容をGRxに格納する} ●

LD GR0, GR1

– _{GR0にGR1の内容を格納} ●

LD GR0, #FF00

– _{アドレス FF00(16進)のメモリの内容をGR0に格納} ●

LD GR0, #FF00, GR1

– _{インデックス修飾：FF00(16進)にGR1の内容を加えた} アドレスの内容を_{GR0に格納 （右端のレジスタは GR1} GR7のみ）

データ転送命令

●

レジスタとレジスタ、レジスタとメモリの間でデータ

を転送する

– _{LD GRx, {GRy | アドレス | アドレス, GRy}} ● 対象をGRxに転送 – _{LAD GRx, {アドレス | アドレス, GRy}} ● 対象のアドレスそのものをGRxに格納 ● LAD GR0, #0010 ; GR0に16を格納 – _{ST GRx, {アドレス | アドレス, Gry}} ● GRxの内容を指定したアドレスのメモリに格納

算術演算・論理演算命令

●

命令

GRx, 対象

GRxと対象を演算し、結果をGRxに格納

– _{ADDA GRx, 対象 ; 算術加算} – _{ADDL GRx, 対象 ; 論理加算} – _{SUBA GRx, 対象 ; 算術減算} – _{SUBL GRx, 対象 ; 論理減算} – _{AND GRx, 対象 ; 論理積} – _{OR GRx, 対象 ; 論理和} – _{XOR GRx, 対象 ; 排他的論理和}

算術加算と論理加算？

●

算術加算

/減算は数値を符号付整数とみなす

●

論理加算

/減算は数値を符号なし整数とみなす

●

16bit符号なし整数： 0~65535

●

16bit符号付整数： -32768~32767

●

違いは何？

– _{符号なし： 32767+1=32768 （問題なし）} – _{符号付： 32767+1 = -32768 （オーバーフロー）} – _{符号なし： 0-1 = 65535 （アンダーフロー）} – _{符号付： 0-1 = -1 （問題なし）}

符号付整数と２の補数表現

●

nビットで数を表現する

– _{8bit符号なし： 0～255} – _{8bit符号付き：-128～127} ●

２の補数による負数の表現

– _{正の数： 00}(16)～7F(16) – _{負の数： FF}(16)～80(16) ● 2の補数表現の利点 – _{通常の加減算がそのまま使える} – _{最上位ビットを見ると数の正負がわかる} 01111111 127 : 00000010 2 00000001 1 00000000 0 11111111 -1 11111110 -2 11111101 -3 : 10000000 -128

2の補数表現

●

ある数の「

2の補数」の求め方（すなわち符号の反

転）

– _{まず「1の補数」を求める：} 2進表現された数の各桁の 1 と 0 を反転する – _{次にその数に1を加える} ●

例：　

-9 を8bit の２の補数表現で表す。

9(10) = 00001001(2) NOT(00001001) = 11110110 11110110 + 1 = 11110111 （答）

演習

●

次の式を

8ビット2進数で計算してみよう。

–

-1+1

–

3+(-5)

演算とフラグ

●

演算結果によってフラグレジスタ

(FR)の内容が

セットされる

– _{FR（3ビット）には OF, SF, ZF （各1ビット）のフラグが含} まれる – _{OF (Overflow Flag)：演算結果がオーバーフローまた} はアンダーフローした時_1になる – _{SF (Sign Flag): 演算結果が負のとき1になる} – _{ZF (Zero Flag): 演算結果が０のとき1になる} ●

条件付き分岐命令で参照される

比較演算命令

●

減算をして結果のフラグだけをセットする（減算結

果は保存されない）

●

CPA GRx, 対象

; 算術比較

●

CPL GRx, 対象

; 論理比較

●

例

– _{CPA GR0, GR1 ; GR0-GR1 を計算} – _{GR0=GR1なら ZFに1がセットされる} – _{GR0<GR1なら SFに1がセットされる}

シフト演算命令

●

レジスタの各ビットを右か左にずらす

– _{SLA GRx, シフト量 ; 算術左シフト　（数値的に2倍）} – _{SRA GRx, シフト量 ; 算術右シフト　（数値的に1/2倍）} – _{SLL GRx, シフト量 ; 論理左シフト　（単純なシフト）} – _{SRL GRx, シフト量 ; 論理右シフト　（単純なシフト）} 算術シフト 0 論理シフト 0 0

シフト演算命令

●

演算例（

8bit）　本当は16bit

元の数値 _{SLA SRA SLL SRL} 00000101 00001010 00000010 00001010 00000010 11110010 11100100 11111001 11100100 01111001 10001111 10011110 11000111 00011110 01000111 算術シフト 0 論理シフト 0 0

分岐命令

●

条件を満たす場合に、指定アドレスから実行

– _{JUMP アドレス ; 指定アドレスから実行する} – _{JPL アドレス ; 演算結果が正の場合} – _{JMI アドレス ; 演算結果が負の場合} – _{JNZ アドレス ; 演算結果が0でない場合} – _{JZE アドレス ; 演算結果が0の場合} – _{JOV アドレス ; オーバーフローが起きた場合} ●

「条件」はフラグレジスタの状態に対応

– _{正：SF=0 かつ ZF=0 負：SF=1} – _{零：ZF=0 非零：ZF=1}

分岐命令

●

どうやって実行順序を変えるのか？

– _{実行アドレスは PR レジスタに格納されている} – _{PR レジスタに値を格納すれば、次はそのアドレスから} 実行が始まる – _{分岐命令はレジスタ間のデータ転送命令の一種}

分岐命令の使用例

0000: 1200 0000 LAD GR0,0 ;GR0=0 0002: 1210 0001 LAD GR1,1 ;GR1=1 0004: 1220 0001 LAD GR2,1 ;GR2=1 0006: 1230 000B LAD GR3,11 ;GR3=11 0008: 2401 ADDA GR0,GR1 ;GR0+=GR1 0009: 2412 ADDA GR1,GR2 ;GR1+=GR2 000A: 4413 CPA GR1,GR3 ;GR1-GR3 000B: 6200 0008 JNZ #0008 ;if not zero 0008

スタック操作命令

●

スタック：各種データを一時保存しておくメモリ

– _{データをスタックに入れる操作(PUSH)と取り出す操作} (POP)が対になる – _{最後に入れたデータが最初に取り出される} ●

PUSH, POP命令

– _{PUSH 値 [, GRy]} ● SPレジスタの値を-1し、SPの示すアドレスのメモリに指定し た値(+GRy)を格納する – _{POP GRy} ● SPレジスタの値が示すアドレスのメモリの内容をGRyに格納 し、_{SPの値を+1する}

PUSHとPOP

10 5 213 FFFF GR0 GR1 GR2 SP FFF8 FFF9 FFFA FFFB FFFC FFFD FFFE FFFF 10 5 213 FFFE 5 10 5 213 FFFD 213 5 10 -53 16 FFFD 213 5 10 -53 213 FFFE 213 5 10 5 213 FFFF 213 5 PUSH 0,GR1 PUSH 0,GR2 途中の処 理でGR1 とGR2の 値が破壊 される POP GR2 POP GR1

サブルーチン命令

●

関数やサブルーチンを実現する

→任意のアドレスから特定のアドレスにジャンプ

し、サブルーチン実行後に元のアドレスに戻ってく

る

– _{CALL アドレス[,GRy]} ● 現在実行中のアドレスの次のアドレスをスタックにPUSH ● 指定したアドレスにジャンプ – _RET ● スタックからアドレスをPOPして、そのアドレスにジャンプ

サブルーチン命令

●

関数やサブルーチンを実現する

→任意のアドレスから特定のアドレスにジャンプ

し、サブルーチン実行後に元のアドレスに戻ってく

る

– _{CALL アドレス[,GRy]} ● 現在実行中のアドレスの次のアドレスをスタックにPUSH ● 指定したアドレスにジャンプ – _RET ● スタックからアドレスをPOPして、そのアドレスにジャンプ

サブルーチン

●

同じ処理をいろいろなところから利用する

: CALL #2000 : : CALL #2000 : 処理内容 : RET 2000 : CALL #2000 : : CALL #2000 : 処理内容 : RET 2000

サブルーチンの実現

: CALL #2000 : : CALL #2000 : 処理内容 : RET 2000 1200 1202 1200 FFFF PR SP FFFD FFFE FFFF 2024 : CALL #2000 : : CALL #2000 : 処理内容 : RET 2000 1200 1202 2000 FFFE 1202 PR SP FFFD FFFE FFFF 2024

サブルーチンの実現

: CALL #2000 : : CALL #2000 : 処理内容 : RET 2000 1200 1202 2024 FFFE 1202 PR SP FFFD FFFE FFFF 2024 : CALL #2000 : : CALL #2000 : 処理内容 : RET 2000 1200 1202 1202 FFFF 1202 PR SP FFFD FFFE FFFF 2024

その他

●

SVC アドレス[,GRy]

– _{アドレスを引数としてシステムコール} – _{何が起きるかはOS依存} – _{OSの機能を呼び出すために使う} ●

NOP

– _{何もしない}

命令コード

●

それぞれの命令に数値が対応する

– _{命令は1ワード(16bit)または2ワード(32bit)} – _{命令語の構成（1ワード目）} OP1 (4) OP2 (4) R1 (4) R2 (4) 0: NOP 1: データ転送命令 2: 加減算命令 3: 論理演算命令 4: 比較命令 5: シフト命令 6: 分岐命令 7: スタック操作命令 8: サブルーチン命令 F: SVC

命令コード

●

算術演算の場合の例

OP1 OP2 R1,R2 命令長 命令 2 0 0~7 2 ADDA R1, addr, R2 1 0~7 2 SUBA R1, addr, R2 2 0~7 2 ADDL R1, addr, R2 3 0~7 2 SUBL R1, addr, R2 4 0~7 1 ADDA R1, R2 5 0~7 1 SUBA R1, R2 6 0~7 1 ADDL R1, R2 7 0~7 1 SUBL R1, R2 ADDL GR0, #FF00, GR3 2203 FF00 SUBA GR2, GR4 2524 ADDA GR2, #1234 2020 1234

プログラム例

●

GR1とGR2に入っている整数の乗算サブルーチン

– _{GR2≧0を仮定} – _{結果はGR0に格納} – _{GR3の内容は破壊される} 0000: 1200 0000 LAD GR0,0 ;GR0←0 0002: 1230 0001 LAD GR3,1 ;GR3←1 0004: 2401 ADDA GR0,GR1 ;GR0←GR0+GR1 0005: 2723 SUBL GR2,GR3 ;GR2←GR2-GR3

0006: 6200 0004 JNZ #0004 ;if not zero goto 0004 0008: 8100 RET ;return

プログラム例

●

GR1とGR2に入っている整数の乗算サブルーチン

– _{GR2,GR3を破壊しないバージョン} 0000: 1200 0000 LAD GR0,0 ;GR0←0 0002: 7002 0000 PUSH 0,GR2 ;GR2を退避 0004: 7003 0000 PUSH 0,GR3 ;GR3を退避 0006: 1230 0001 LAD GR3,1 ;GR3←0 0008: 2401 ADDA GR0,GR1 ;GR0←GR0+GR1 0009: 2723 SUBL GR2,GR3 ;GR2←GR2-GR3

000A: 6200 0008 JNZ #0008 ;if(not zero) goto #0008 000C: 7130 POP GR3 ;GR3を復帰

000D: 7120 POP GR2 ;GR2を復帰 000E: 8100 RET ;return

演習

●

これは何をするプログラムか説明せよ。

– _{入力は GR1（アドレス）、GR2（正の整数）} – _{出力は GR3（整数）} – _{0011番地の 1 は定数} 0000: 1031 0000 LD GR3,0,GR1 0002: 2210 0011 ADDL GR1,#0011 0004: 2320 0011 SUBL GR2,#0011 0006: 6300 0010 JZE #0010 0008: 4031 0000 CPA GR3,0,GR1 000A: 6500 0002 JPL #0002 000C: 1031 0000 LD GR3,0,GR1 000E: 6400 0002 JUMP #0002 0010: 8100 RET

機械語とニモニック

●

計算機は機械語（数字で表される命令列）で動く

– _{12000000700200007003000012300001240127236} 2000008713071208100 ●

これではわかりにくいので、命令を表現する記号

（ニモニック、

_{mnemonic）でプログラムを書く}

– _{動作との対応がつけやすい} – _{機械語とニモニックは1対1対応} – _{機械語列にするには変換が必要} LAD GR0,0 LAD GR3,1 ADDA GR0,GR1 SUBL GR2,GR3 JNZ #0004 RET Mnemonic: 記憶術

アセンブリ言語

●

ニモニックから機械語への変換：アセンブル（組立）

– _{表参照と簡単なルールで変換できる} ●

もっと便利に：アセンブリ言語

– _疑似命令 ● プログラム開始・終了の宣言 ● 定数領域・データ領域の宣言 – _ラベル ● ジャンプ先やデータのアドレスを自動計算 – _マクロ ● よく使う命令列を1行で表現する

機械語への変換は

アセンブラ

が行う

アセンブリ言語の例

; GR1とGR2の掛け算

MULT

START

LAD GR0,0

LOOP

ADDA GR0,GR1

SUBL GR2,

ONE

JNZ

LOOP

RET

ONE

DC

1

END

ラベル 疑似命令 コメント

アセンブリ言語

●

疑似命令

– _{命令と同じ形式で記述されるが、命令そのものではな} い – _{START: プログラムの最初を指定する（ラベル必須）} – _{END: プログラムの終わりを指定する} – _{DC: 定数を定義する} メモリ上にその数字が格納されるが、命令ではない – _{DS: データ領域を定義する} メモリ上に指定した語数の領域が確保される。 データ処理などに使う用途

アセンブリ言語

●

ラベル

– _{プログラム内のアドレスやデータのアドレスを記号で参} 照する ● 実際のアドレスへの変換はアセンブラが行う ● 命令を挿入・削除した時にも変更しなくてよい ●

マクロ

– _{よく使う複数の命令列を1つの命令のように書ける} ● IN アドレス,長さ 指定したメモリにデータを入力 ● OUT アドレス,長さ 指定したメモリの内容を出力 ● RPUSH 全レジスタをPUSH ● RPOP 全レジスタをPOP

アセンブリ言語

●

定数の記述

– _{定数は演算などに頻繁に使うので、あたかも定数を直} 接演算できるかのように書ける MULT START LAD GR0,0 LOOP ADDA GR0,GR1 SUBL GR2,=1 JNZ LOOP RET END MULT START LAD GR0,0 LOOP ADDA GR0,GR1 SUBL GR2,CONST1 JNZ LOOP RET CONST1 DC 1 END 自動 生成

アセンブラによる処理

アセンブリ言語 のプログラム アセンブラ のプログラム機械語 リンカ ライブラリ 実行可能 プログラム

演習

● アセンブリ言語を使い、下記のプログラムをわかりやすく記述せよ。 – _{疑似命令:　START, END} – _ラベル – _定数演算 0000: 1031 0000 LD GR3,0,GR1 0002: 2210 0011 ADDL GR1,#0011 0004: 2320 0011 SUBL GR2,#0011 0006: 6300 0010 JZE #0010 0008: 4031 0000 CPA GR3,0,GR1 000A: 6500 0002 JPL #0002 000C: 1031 0000 LD GR3,0,GR1 000E: 6400 0002 JUMP #0002 0010: 8100 RET

アセンブリ言語によるプログラミング

●

CASL-IIを使ってさまざまなプログラムを書いてみ

る

– _{通常は高級言語(Cなど)で書く操作をアセンブラで書い} たらどうなるか – _{コンピュータの基本的な動きを理解する}

高速な乗算

●

加算を繰り返す乗算は簡単だが効率が悪い

– _{a×b=(a+a+...+a) aをb回加算} ●

筆算の要領で計算する

– _{乗算の値によらず、桁数に比例する計算で済む} 00101010 X 01101000 ---00101010 00101010 00101010 ---01000100010000 42 X 104 ---168 42 4368

高速な乗算

●

アルゴリズム（

Z←A×B)

Z←0 For i=16 to 1 by -1 If Bの最下位ビットが1 then Z←Z+A End if A←A*2 B←B/2 End for 00101010 X 01101000 ---00101010 00101010 00101010 ---01000100010000

高速な乗算

i A B Z 1 00101010 01101000 0 2 001010100 0110100 0 3 0010101000 011010 0 4 00101010000 01101 00101010000 5 001010100000 0110 00101010000 6 0010101000000 011 0011010010000 7 00101010000000 01 001000100010000 8 001010100000000 0 001000100010000

注意点

●

GR2の下1ビットを取り出す

– _{AND GR2,=1} – _{これを実行するとGR2の内容が破壊される} – _{GR2の内容を保存したい場合は別なレジスタを使う} – _{LD GR4,GR2} – _{AND GR4,=1} ●

GR1の値を2倍する

– _{SLA GR1,1 ; 1ビット算術左シフト} ●

GR2の値を1/2倍する

– _{SRA GR2,1 ; 1ビット算術右シフト}

アセンブリ言語で書いてみる

●

Z: GR0, A: GR1, B: GR2, i: GR3 とする

FMULT START LAD GR0,0 ; GR0←0 LAD GR3,16 ; GR3←16 LOOP LD GR4,GR2 ; G4←G2 AND GR4,=1 ; G4←G4 and 1

JZE SKIP1 ; if not zero then

ADDA GR0,GR1 ; G0←G0+G1

SKIP1 SLA GR1,1 ; G1←G1*2

SRA GR2,1 ; G2←G2/2

SUB GR3,=1 ; G3←G3-1

JNZ LOOP ; if not zero goto LOOP

RET ; return

再帰呼び出しによる計算

●

C言語でよくあるやつ

int factorial(int n) { if (n == 0) return 1 return n*factorial(n-1) } ●

さっきの

FMULTを使ってみる

– _{FMULTはGR1,GR2を入力としてGR0を出力とする} GR4を破壊する

再帰呼び出しによる計算

●

GR5を入力、GR0を出力とする

●

基本的な考え方

– _{GR5が0ならGR0に1を代入して終了} – _GR5を退避 – _{GR5を1減らして階乗を計算→GR0} – _GR5を復帰 – _{GR5とGR0の積をGR0に代入して終了}

プログラム

FACT START

CPA GR5,=0 ; GR5-0

JNZ SKIP2 ; if zero then LAD G0,1 ; GR0←1 RET ; return SKIP2 PUSH 0,GR5 ; GR5を保存 SUBA GR5,=1 ; GR5←GR5-1 CALL FACT ; GR0←GR5の階乗 LD GR1,GR0 ; GR1←GR0 POP GR5 ; GR5を復帰 LD GR2,GR5 ; GR2←GR5 CALL FMULT ; GR0←GT1*GR2 RET ; return END

メモリの内容の探索

●

GR1から始まるGR2個のメモリの中にGR3の内容

があるかどうかをチェック

●

存在する場合には

GR0にアドレスを返す

●

存在しない場合には

GR0に0を返す

アドレス 値 8000 23 8001 5 8002 323 8003 532 8004 34 8005 322 8006 167 GR1=#8000,GR2=7,GR3=34 →GR0=#8004 GR1=#8000,GR2=4,GR3=34 →GR0=0 GR1=#8000,GR2=7,GR3=322 →GR0=8005

アルゴリズム

While GR2 > 0

If M[GR1] = GR3 then

GR0←GR1

Return

End if

GR2←GR2-1; GR1←GR1+1

End while

GR0←0

return

プログラム

SEARCH START

LOOP CPL GR2,=0 ; GR2-0

JNZ SKIP1 ; if zero then JUMP BREAK ; goto BREAK SKIP1 CPA GR3,0,GR1 ; GR3-M[GR1]

JNZ SKIP2 ; if zero then LD GR0,GR1 ; GR0←GR1

RET ; return

SKIP2 ADDL GR1,=1 ; GR1←GR1+1 SUBL GR2,=1 ; GR2←GR2-1 JUMP LOOP ; goto LOOP BREAK LAD GR0,0 ; GR0←0

RET ; return

演習

●

メモリ領域をコピーするプログラムを書け。

– _{GR0が指すアドレスからGR2の個数分のメモリをGR1} が指すアドレス移行にコピーする。 – _{GR0～GR0+GR2の領域とGR1～GR1+GR2の領域} には重なりがないものとする。 – _例 アドレス 内容 アドレス 内容 8000 48 8100 00 8001 65 8101 00 8002 6C 8102 00 8003 6C 8103 00 8004 6F 8104 00 8005 2C 8105 00 8006 77 8106 00 8007 6F 8107 00 8008 72 8108 00 GR0=#8000 GR1=#8100 GR2=5 でプログラム起動⇒

演習

●

メモリ領域をコピーするプログラムを書け。

– _{GR0が指すアドレスからGR2の個数分のメモリをGR1} が指すアドレス移行にコピーする。 – _{GR0～GR0+GR2の領域とGR1～GR1+GR2の領域} には重なりがないものとする。 – _例 アドレス 内容 アドレス 内容 8000 48 8100 48 8001 65 8101 65 8002 6C 8102 6C 8003 6C 8103 6C 8004 6F 8104 6F 8005 2C 8105 00 8006 77 8106 00 8007 6F 8107 00 GR0=#8000 GR1=#8100 GR2=5 でプログラム起動⇒

演習の方針

（必ずしもこの通りでなくてもよい）

1.GR0の指すメモリの内容をGR3にコピー (LD)

2.GR3の内容をGR1の指すメモリにコピー (ST)

3.GR0に1を加える (ADDL)

4.GR1に1を加える (ADDL)

5.GR2から1を引く (SUBL)

6.0でなければ1.へ (JNZ)

7.RET

高級言語

●

アセンブリ言語の問題点

– _{実現したい計算とCPUの機能が違う} →複数の命令の組み合わせで_{1つの処理をする} →わかりにくい – _{CPUによって命令が異なる} →ある計算機のプログラムをほかの計算機で使えない ●

高級言語

– _{「計算したい内容」を直接記述→自動的に機械語に変} 換 – _{人間にとって記述が容易} – _{変換プログラムをCPUごとに書けば、高級言語のプロ}

初期の高級言語

●

FORTRAN (1955)

– _{数値計算言語} – _{計算を数式で記述できる(FORmula TRANslator)} – _{装置と直接対応する入出力（プリンタ、カードリーダ、} キーボード、磁気テープなど） – _{GOTO文による実行制御} ●

LISP (1958)

– _{記号とその並び（リスト）を処理する(LISt Processor)} – _{関数型言語、括弧（）を使った記述} – _{今なお使われる柔軟性}

初期の高級言語

●

COBOL (1959)

– _{ビジネス処理用言語}

(COmmon Business Oriented Language)

– _{表の入出力と集計（現在の表計算処理に近い）} – _{読みやすさ重視}

● プログラムの説明文が言語仕様に含まれる ● 自然言語に近い命令文

いろいろなプログラム言語

●

ユークリッドの互除法を実装してみる

GCD(m,n):

If (n=0) then m

Else GCD(n,m mod n)

GCD(m,n):

while (n≠0)

t←n

n←m mod n

m←t

End while

Return m

Fortran (1954)

下のコードは

Fortran 66 (1966)

M=100 N=72 10 IF (N) 20,30,20 20 CONTINUE I=N N=M-INT(REAL(M)/REAL(N))*N M=I GOTO 10 30 WRITE(6,40) M 40 FORMAT(1H ,I5) STOP END

Fortran (1954)

下のコードは

Fortran 95 (1995)

program GCD integer::euclid_gcd integer::m,n m = 100 n = 72 Print *, euclid_gcd(m,n) end program

integer function euclid_gcd(m,n) integer::m,n integer::t do while (n /= 0) t = n n = mod(m,n) m = t end do gcd = m return end function

LISP (1958)

コードは

Common Lisp (1984)

(defun euclid-gcd (m n)

(if (= n 0) m

(euclid-gcd n (mod m n))

)

)

(print (euclid-gcd 100 72))

COBOL (1959)

IDENTIFICATION DIVISION.

PROGRAM-ID. EUCLID-GCD. AUTHOR. AKINORI ITO.

DATE-WRITTEN. 2018/6/10. DATE-COMPILED. 2018/6/10. ENVIRONMENT DIVISION. CONFIGURATION SECTION. DATA DIVISION. WORKING-STORAGE SECTION. 01 M PICTURE 99999. 01 N PICTURE 99999. 01 T PICTURE 99999. 01 X PICTURE 99999. PROCEDURE DIVISION. MOVE 100 TO M. MOVE 72 TO N. PERFORM UNTIL N = 0 MOVE N to T

DIVIDE M BY N GIVING X REMAINDER N MOVE T to M

END-PERFORM. DISPLAY M.

BASIC（1964）

下のコードは

Chipmunk Basic (1990)

10 m=100:n=72

20 if n<>0 then goto 40

30 print m:end

40 t=n: n=m mod n: m=t

50 goto 20

Pascal (1970)

Program GCD(output);

function euclid_gcd(m:integer; n:integer):integer; var t:integer; begin if n=0 then euclid_gcd := m else begin t := euclid_gcd(n, m mod n); euclid_gcd := t end end; begin writeln(euclid_gcd(100,72)); end.

C (1972)

下のコードは

ANSI-C (1990)

#include <stdio.h>

int euclid_gcd(int m, int n) { if (n == 0) return m; return euclid_gcd(n, m%n); } int main() { printf("%d\n",euclid_gcd(100,72)); return 0; }

C++ (1983)

#include <iostream> using namespace std;

int euclid_gcd(int m, int n) { if (n == 0) return m;

return euclid_gcd(n, m%n); }

int main() {

cout << euclid_gcd(100,72) << endl; return 0;

Perl (1987)

sub euclid_gcd { my ($m, $n) = @_; if ($n == 0) { return $m; } return euclid_gcd($n, $m%$n); } print euclid_gcd(100,72);

Tcl (1988)

proc euclid_gcd {m n} { if {$n == 0} {

return $m } else {

return [euclid_gcd $n [expr $m%$n]] }

}

Haskell (1990)

euclid_gcd m 0 = m

euclid_gcd m n = euclid_gcd n (m `mod` n) main = print (euclid_gcd 100 72)

Python (1991)

def euclid_gcd(m,n):

if n==0:

return m

return euclid_gcd(n,m%n)

print(euclid_gcd(100,72))

Ruby (1993)

def euclid_gcd(m,n) if n==0 then return m else return euclid_gcd(n,m%n) end end print euclid_gcd(100,72),"\n"

Lua (1993)

function euclid_gcd(m,n)

if n==0 then

return m

else

return euclid_gcd(n,m%n)

end

end

print(euclid_gcd(100,72))

Java (1995)

public class Main {

public static int euclid_gcd(int m, int n) { if (n == 0) return m;

return euclid_gcd(n,m%n); }

public static void main(String []args){

System.out.println(euclid_gcd(100,72)); }

JavaScript (1995)

function euclid_gcd(m,n) { if (n == 0) { return m; } return euclid_gcd(n,m%n); } console.log(euclid_gcd(100,72));

R (1996)

euclid.gcd <- function(m,n) {

if (n==0) {

return(m)

}

return(euclid.gcd(n,m%%n))

}

cat(euclid.gcd(100,72))

C# (2000)

using System.IO; using System;

class Program {

static int Euclid_GCD(int m, int n) { if (n==0) return m;

return Euclid_GCD(n,m%n); }

static void Main() {

Console.WriteLine(Euclid_GCD(100,72)); }

Go (2009)

package main import "fmt"

func euclid_gcd(m int, n int) int { if (n==0) { return m } return euclid_gcd(n,m%n) } func main() { fmt.Printf("%d\n",euclid_gcd(100,72)) }

Julia (2012)

function euclid_gcd(m,n)

if n==0

m

else

euclid_gcd(n,m%n)

end

end

println(euclid_gcd(100,72))

高級言語の実現方式

●

コンパイラ

– _{高級言語のプログラムを読み込み、それを機械語に変} 換して、単独で動く機械語の実行形式ファイルを生成す る – _{実行は高速、できたプログラムはCPU依存} – _{デバッグが面倒（動いているプログラムとソースプログ} ラムの対応がつけにくい） ソース プログラム コンパイラ オブジェクト プログラム （機械語） リンカ ライブラリ 実行可能 プログラム

高級言語の実現方法

●

インタプリタ

– _{高級言語のプログラムを読み込み、その内容を直接実} 行する （高級言語に対応する機械語のプログラムは生成され ない） – _{実行は遅く、プログラムのCPU依存性は少ない} – _{実行状況が把握しやすい} ソース プログラム インタプリタ 直接 実行

高級言語の実現方法

●

中間言語（バイトコード）コンパイラ

– _{仮想的なCPUの機械語にコンパイル→CPUエミュレー} タ（仮想マシン、_{VM）による実行} – _{実行する計算機のCPUに依存せず、インタプリタより速} い（コンパイラより遅い） ソース プログラム コンパイラ オブジェクト プログラム （機械語） バイトコード エミュレータ （仮想マシン） 直接 実行

代表的な高級言語と実現方法

コンパイラ

インタプリタ

中間言語

Fortran LISP* C C++ Objective-C LISP* BASIC Perl Ruby Python* JavaScript PHP Smalltalk Java Python* C#

コンパイラのお仕事

●

ソースプログラムから最終的な機械語（コード）を生

成するには段階がある

ソース プログラム 中間表現 コード 最適化コード 構文解析・ 変換ルール コード生成 ルール 最適化 ルール

構文解析

●

単なる文字列であるソースプログラムから構造を

見つけ出す

a=b+1;

プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木

構文解析ルールの例

●

プログラム：文

●

プログラム：プログラム 文

●

文：変数

= 式;

●

式：変数

●

式：定数

●

式：式

+ 式

●

式：式 – 式

●

式：

(式)

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

構文解析ルールと構文木

● プログラム：文 ● プログラム：プログラム 文 ● 文：変数 = 式; ● 式：変数 ● 式：定数 ● 式：式 + 式 ● 式：式 – 式 ● 式：(式) プログラム 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 構文木が_{1段下がる部分は構文解析ルール1つと対応する}

演習

●

次のプログラムの構文木を示せ。

構文木から中間表現へ

●

さまざまな中間表現がある

– _{ここでは「四つ組」を紹介} ●

四つ組：（演算　対象１　対象２　格納先）

元の文 四つ組 y=x+1 (+, x, 1, y) z=x+y+2 (+, x, y, T1) (+, T1, 2, z) x=a+b*c (*, b, c, T1) (+, a, T1, x) x=1 (=, 1, ,x) T1は中間変数 （自動的に確保される） 必要に応じて_{T2, T3 なども} 使う

構文木から中間表現へ

●

機械的な四つ組生成

– _{「変数=式;」の場合、} ● 式の四つ組を生成 ● 値が格納された中間変数をTと するとき、(=, T, ,変数) を生成 – _{「式1+式2」の場合、} ● 式1の四つ組を生成し、中間変 数T1に格納 ● 式2の四つ組を生成し、中間変 数T2に格納 ● 自動生成された中間変数をTと するとき、(+, T1, T2, T) を生成 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

機械的な四つ組生成

– _{「変数」の場合、} ● 中間変数をTとすると (=, 変数, ,T) を生成 – _{「定数」の場合、} ● 中間変数をTとすると (=, 定数, ,T) を生成 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{式の部分の四つ組を生成} して_T1に格納 – _{T1を変数に格納} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{式の部分の四つ組を生成} して_T1に格納 – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{左の式の四つ組を生成してT2} に格納 – _{右の式の四つ組を生成してT3} に格納 – _{(+, T2, T3, T1)} – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{変数の内容をT2に格納} – _{右の式の四つ組を生成してT3} に格納 – _{(+, T2, T3, T1)} – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{(=, b, ,T2)} – _{右の式の四つ組を生成してT3} に格納 – _{(+, T2, T3, T1)} – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{(=, b, ,T2)} – _{定数をT3に格納} – _{(+, T2, T3, T1)} – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から中間表現へ

●

生成例

– _{(=, b, ,T2)} – _{(=, 1, ,T3)} – _{(+, T2, T3, T1)} – _{(=, T1, ,a)} 文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1

構文木から

4つ組の生成

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 ●

準備

– _{構文木の節点（ノード）} Node n; – _{節点の子節点} n.child(k) – _{節点の種類} n.type == “文”

構文木から

4つ組の生成

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 ●

準備

– _{構文木の節点（ノード）} Node n; – _{節点の子節点} n.child(k) – _{節点の種類} n.type == “文”

構文解析ルールの例

●

プログラム：文

●

プログラム：プログラム 文

●

文：変数

= 式;

●

式：変数

●

式：定数

●

式：式

+ 式

●

式：式 – 式

4つ組生成手続き（文）

Generate(Node n) {

If (n.type == “式” and

n.child.type == (“変数” “=” “式” “;”)) { tmpvar = 一時変数名

GenerateExpression(n.child(2), tmpvar) Output(“=”, tmpvar, null, n.child(0))

} }

4つ組生成手続き（式）

GenerateExpression

(Node n, String tmpvar) {

If

(n.child(0).typeが “変数” または “定数”) {

Output

(“=”,n.child(0).child(0), null,tmpvar)

}

Else if

(n.child(1).type が “+” または “-”) {

t1 = 一時変数名; t2 = 一時変数名

GenerateExpression

(n.child(0), t1)

GenerateExpression

(n.child(2), t2)

Output

(n.child(1).type, t1, t2, tmpvar)

}

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n.child(2), tmpvar)

Output(“=”, tmpvar, null, n.child(0)) _n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1")

Output(“=”, tmpvar, null, n.child(0)) _n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1")

Output(“=”, "T1", null, n.child(0))

n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1")

Output(“=”, "T1", null, n.child(0))

n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n.child(0).child(0), null,"T2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1

n2 n3 n4 n5

n6 n7 n8 n9

n10 n11

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2) (=, 1, , T3)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output(n.child(1).type, "T2", "T3", "T1")

Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2) (=, 1, , T3)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1")

Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2) (=, 1, , T3) (+, T2, T3, T1)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))

n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2) (=, 1, , T3) (+, T2, T3, T1)

4つ組の生成例

文 変数 = 式 ; a _{式 + 式} 変数 b 定数 1 Generate(n1) GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1") Output(“=”, "T1", null, a) n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 (=, b, , T2) (=, 1, , T3) (+, T2, T3, T1) (=, T1, ,a)

効率の良い中間表現生成

●

前ページの中間表現は実は

1行で書ける

– _{(+, b, 1, a)} – _{最初からこういう中間表現を生成するには？} – _{中間表現の生成ルールを細かくする} – _{中間表現を生成した後、コードの無駄を省く処理を行う} （最適化）

細かいコード生成ルール

●

「式

1＋式2」の場合

– _{最後に格納する一時変数をT1とする} 式_1の先 変数 定数 その他 式2の 先 変数 (+,変数1,変数2,　 T1） (+,定数1,変数2,　T1） 式1の四つ組を生成し てT2に格納 (+,T2,変数2,T1) 定数 (+,変数1,定数2,　 T1） (+,定数1,定数2,　T1） 式1の四つ組を生成し てT2に格納 (+,T2,定数2,T1) その他 式1の四つ組を生成 してT2に格納 (+,T2,変数2,T1) 式1の四つ組を生成 してT2に格納 (+,T2,定数2,T1) 式1の四つ組を生成し てT2に格納 式2の四つ組を生成し てT3に格納 (+,T2,T3,T1)

最適化の例

●

中間表現があるパターンに合致する場合には置き換

えを行う

– _{例：ある一時変数に何かを代入し、そのあとその一時変数} が_{1回しか使われていなければ、後者の一時変数を前者} の変数または定数に置き換える。 – _{ある一時変数に結果を代入し、それをすぐに別な変数に} 代入しているとき、一時変数をその変数に置き換える。 (=, x, ,T3) : (+, T3, T4, T2) (=, x, ,T3) : (+, x, T4, T2) (+, x, y, T1) (=, T1, , z) (+, x, y, (=, T1, ,z)z)

最適化の例

(=, b, ,T2) (=, 1, ,T3) (+, T2, T3, T1) (=, T1, ,a) (=, b, ,T2) (=, 1, ,T3) (+, b, T3, T1) (=, T1, ,a) (=, 1, ,T3) (+, b, T3, T1) (=, T1, ,a) (=, 1, ,T3) (+, b, 1, T1)

コード生成

●

四つ組の列を命令列に変換

– _{変換ルール例}

四つ組

ニモニック

(=, X, , Y) LD G0,X ST G0,Y (+, X, Y, Z) LD G0,X ADDA G0,Y ST G0,Z (-, X, Y, Z) LD G0,X SUBA G0,Y ST G0,Z

コード生成例

高級言語 中間言語 生成コード

X=Y+1; (+,Y, 1, X) LD G0,Y

ADDA G0,=1 ST G0,X Z=X+Y-2; (+, X, Y, T1) (-, T1, 2, Z) LD G0, XADDA G0, Y ST G0, T1 LD G0, T1 SUBA G0, =2 ST G0, Z

演習

●

Z=X+Y-2 からコード生成が行われるまでの処理を

記述せよ。

– _構文木 – _{四つ組の生成} – _最適化 – _{コード生成}

データ表現とデータ構造

●

コンピュータは数字しか扱えない

– _{メモリの１つの番地には一定範囲の整数しか格納でき} ない – _{8ビットなら0～255，または-128～127} ●

それ以外のデータはどうやって表現されているの

か？

– _実数 – _{文字と文字列} – _{マルチメディアデータ（画像，音声）}

整数

●

符号なし

nビット整数　0～2

n

-1

●

符号付き

nビット整数　-2

n-1

～

2

n-1

-1

ビット長 符号なし 符号付き 8 (char) 0～255 -128～127 16 (short) 0～65535 -32768～32767 32 (long) 0～4294967295 -2147483648～ 2147483647 64 (long long) 0～18446744073709551 615 -9223372036854775808～ 9223372036854775807

実数

●

固定小数、有理数、浮動小数

– _{固定小数：小数点の上と下の精度が固定} – _{有理数：整数の比} ● 数式処理などでは使われるが、あまり一般的でない – _{浮動小数：小数点の位置が変動} ● 6.0221413×1023のような形式 ●

多くの場合浮動小数形式が使われる

固定小数表現

●

小数点の上と下の精度が固定

– 32ビット固定小数　-8000.0000～7FFF.FFFF₁₆ 10進では-32768.0～32767.9999847412109375 – 最小精度 0.0001₁₆=0.0000152587890625₁₀ ●

利点：計算が簡単

– _{基本的に通常の整数演算と同じ} ●

欠点：表せる数値の範囲が限られる

●

限られた範囲の数だけを高速に表現する用途に使

われる

– _{信号処理チップなど}

浮動小数表現

●

数値の有効桁数を一定にする表現方法

– _{6.0221413×10}23のような形式 – _{符号s×仮数a×基数b}指数p_{の形式で表される} – _{通常1≤a<2, b=2, s=1 or -1} s _{p a} ビット長 _{s p a 有効桁} 数 32 (float) 1 8 23 7.22 64 (double) 1 11 52 15.95 128 1 15 112 34.02

IEEE形式浮動小数

●

16, 32, 64, 128bit

●

s=0 （正の数）またはs=1（負の数）

●

指数部はバイアス表現

– _-2n-1_+2～2n-1_{-1を表現、整数の2}n-1_{-1を0とする} ● 表したい数値に2n-1-1を加える – 8ビットの場合、01₁₆が-126, 7F₁₆が0,FE₁₆が127 ●

「数でないもの」の表現

– オーバーフローを表す +Inf, -Inf (p=FF₁₆, a=0) – Not a Number (NaN) (p=FF₁₆, a≠0)

IEEE形式浮動小数

●

例：

-3.5をIEEE形式32ビット浮動小数にする

– _{負の数なのでs=1} – 3.5=7.0×2-1 より、3.5=111₂×2-1=11.1₂ – 11.1₂=11.1₂×20=1.11₂×21より、a=1.11₂, p=1 – _{pをバイアス表現にし(127を加え）て2進数にすると} ● p=10000000 2 – _{sが1ビット、pが8ビット、aが23ビット（aの先頭の1.を除く）} →_{1100 0000 0110 0000 0000 0000 0000 0000}

演習

●

4.125をIEEE形式32ビット浮動小数で表せ。

a) 符号_{sを決める} b) 4.125を小数点付き2進数に変換する。 c) それを_{1以上2未満の数a×2}pの形にする。 d) pを8ビットのバイアス表現に変換。 e) s（1ビット）、p（8ビット）、a（23ビット）を並べる。 a) aの先頭の1.は省く b) 23ビットに満たない部分は右に0を詰める

浮動小数演算

●

浮動小数の形式に合わせるため、複雑な計算が

必要

●

x1=(s1,a1,p1)とx2=(s2,a2,p2)の加算

– _{（簡単のためs1=s2、p1>p2と仮定する）}

a2←a2/2

p1-p2

a←a1+a2, p←p1, s←s1

while a>2

a←a/2, p←p+1

return (s,a,p)

浮動小数演算

●

x1=(s1,a1,p1)とx2=(s2,a2,p2)の乗算

　　

_s←s1×s2

p←p1+p2

a←a1×a2

while a>2

a←a/2, p←p+1

return (s,a,p)

文字の表現

●

整数と文字を対応させる（符号化）

●

文字セット（文字集合）：表現すべき文字の集合

– _{言語に依存する} – _{多くの言語が同時に表現できる文字セットもある} ●

文字コード（文字符号）：文字セット内の文字と数字

の対応（またはその数字）

– _{1つの文字セットに対して文字コードが複数ある場合も} ある

文字セット

●

表現すべき文字の集合

●

英語

– _{US-ASCII: アルファベット、数字、記号} ●

日本語

– _{JIS X0201: アルファベット＋記号・数字＋カタカナ（い} わゆる半角カナ） – _{JIS X0208: 漢字＋記号（いわゆる全角記号）} – _{JIS X0213: 補助漢字} ●

多言語

US-ASCII

●

英語のための代表的な文字セット・文字コード

– _{American Standard Code for Information}

Interchange の略

US-ASCII

20 sp 30 0 40 @ 50 P 60 ` 70 p 21 ! 31 1 41 A 51 Q 61 a 71 q 22 “ 32 2 42 B 52 R 62 b 72 r 23 # 33 3 43 C 53 S 63 c 73 s 24 $ 34 4 44 D 54 T 64 d 74 t 25 % 35 5 45 E 55 U 65 e 75 u 26 & 36 6 46 F 56 V 66 f 76 v 27 ' 37 7 47 G 57 W 67 g 77 w 28 ( 38 8 48 H 58 X 68 h 78 x 29 ) 39 9 49 I 59 Y 69 i 79 y 2A * 3A : 4A J 5A Z 6A j 7A z 2B + 3B ; 4B K 5B [ 6B k 7B { 2C , 3C < 4C L 5C \ 6C l 7C | 2D - 3D = 4D M 5D ] 6D m 7D } 2E . 3E > 4E N 5E ^ 6E n 7E ~ 2F / 3F ? 4F O 5F _ 6F o 7F DEL

文字コード（文字符号化方式）

●

文字セット中の文字には番号が振られているが、

それをどうやってコンピュータ上で表現するかは別

途規定される（文字符号化方式）

●

日本語の場合

– _{文字セット：JIS X0201+X0208+X0213} – _{文字コード} ● ISO-2022-JP ● Shift-JIS ● EUC-JP