５．５ 実行時のデータの扱い （１）機械語におけるデータ表現

Presentation on theme: "５．５ 実行時のデータの扱い （１）機械語におけるデータ表現"— Presentation transcript:

1 ５．５ 実行時のデータの扱い （１）機械語におけるデータ表現
５．５　実行時のデータの扱い （１）機械語におけるデータ表現 ①レジスタ ②メモリ 　番地付けされたバイトまたはワードの配列 命令の選択によって、整数として、浮動小数点、文字、ビット等として扱う。 データをどう表現するか、どのように割り付けるかは コンパイラの役割である。

2 （２）データ型の内部表現 ① 整数、浮動小数点、文字等は計算機ハードウェア表現を用いる。
② ハードウェアとして用意されていないデータ表現は、コンパイラで取扱いを定める。

3 （a）整数 ① 通常は１語（計算機によって４バイト、２バイト） ② 負の数は２の補数表現
(000E16) －１　　 (FFFF16) －２　　 (FFFE16) 　　　・ －10　　 (FFFD16) －11　　 (FFFC16)

4 整数表現 ２バイト整数 -32,768 ～ +32,767 ４バイト（32ビット）整数
２バイト整数　-32,768 ～ +32,767 整数表現 符号（１ビット） ２の補数（15ビット） ４バイト（32ビット）整数 　-2,147,483,648 ～ -2,147,483,647 符号（１ビット） ２の補数（31ビット） -32,768 （ザン(3)ニー(2)チー(7)ロン(6)パー(8)） -2,147,483,648 （婦人（フヒト(21）)のような(47)弱さ(483)虫歯（648）

5 （b）浮動小数点 計算機別に用意されている表現を用いる。 通常は4バイト。倍長や4倍長がある。 整数
①通常は１語（計算機によって４バイト、２バイト） ②負の数は２の補数表現 【２バイト（16ビット）の場合】 　-32,768(= -215)～+32,767(= ) （ザン(3)ニー(2)チー(7)ロン(6)パー(8)） 【４バイト（32ビット）の場合】 　-2,147,483,648 (= -231)～2,147,483,648 (= 231-1) （婦人（フヒト(21）)のような(47)弱さ(483)虫歯（648）

6 小数（浮動小数点）2進数表現 浮動小数点数の形式（コンピュータによって異なる） （注）以下の例は4バイト(32ビット）だが
8バイト(64ビット：倍精度)もある 符号（ 1 ビット） 指数（ 7 ビット） 指数仮数（24 ビット） 符号 ： 0のとき非負，1のとき負 指数(n) ： 2の補数表現（先頭ビットは符号） 仮数(α) ： 絶対値　1≦α＜1

7 小数の2進数表現例 たとえば であるから 　　 16進数で表記すれば，00 D

8 （c）論理値 原理的には1ビットで十分だが、アクセス速度を考え 1バイトか1語で表現される。表現方法は様々。 【Trueの値】
(1バイトの場合）　　　　　　（1ワードの場合）

9 （d）文字 8 ビット系 ASCII、EBCDIC 16ビット系 JISコード、シフトJIS EUC(Extended UNIX Code)
左のテキストファイルを バイナリファイルとして読み込むと， 以下のようになる

10 ASCIIコード表 CR:Carriage Return LF:Line Feed テキストが 16進数で 表示され てるね。 なお，
0Dは[CR] 0Fは[ＬＦ］

11 ＪＩＳ第一水準のコード 日本語文字は 2byteで表現 するんだ

12 （e）配列 ①同一型のデータの集まり（位置は添え字で指定） X[j] x + s × j x : X[j]の先頭アドレス
　　　s : Xの1要素のサイズ ②2次元の場合、 X[m, n] (Cの場合 X[m][n])で宣言 X[i,j]　 x　+　s × n × i + s ×　j 　 x : X[i, j]の先頭アドレス

13 （f）構造体/ユーザ定義型/レコード型 異なるデータの集まり（位置は要素名で指定）
　　　struct { int p; char c, double f;} 【注】 境界合せ（boundary alignment）が必要な場合、境界をワード、ダブルワードサイズの整数倍に合わせる必要がある。

14 境界合せが必要な場合と不要な場合 struct { int p; char c, double f;} 境界合せが不要な場合
Ada では、これをソースプログラムで指定可能。これを表現仕様（representation specification）という。

15 （g）文字列 Pascal 文字を要素とする固定長の1次元配列 C 最後尾に値 0 の 1バイトを置く可変長の文字列。
Prolog　文字のリスト

16 （h）ポインタ 機械語では番地として扱う。 サイズは機械によって異なる。 基本的には整数と同じで加減算のみが可能。
■昨今の言語では、ポインタの概念を除外（Java）したり、使う場合は使うことを宣言させることで制限を加える(C#)ことが多い。

17 （３）変数と一時変数 ① ソースプログラム上のデータ（変数や定数）は主記憶上に割り当てる。
② ただし、命令語中に埋め込むことが可能な小さい整数は、命令語中のオペランドとして埋め込まれる場合もある。 ③ 式の計算途中結果を保存するためにコンパイラが生成する一時変数（temporary variable, work variable）は、主記憶上に割り当てる場合と、レジスタ上に保持するだけのものもある。

18 MC68000での生成法の違い A = (B + C) * (D - E) MOV B, R0 ADD C, R0 MOV R0, Temp
MOV D, R0 SUB E, R0 MUL Temp, R0 MOV R0, A ・ Temp DA 1 MOV B, R0 ADD C, R0 MOV D, R1 ‘ Tempの替わり SUB E, R1 ‘ R1を使用 MUL R1, R0 MOV R0, A （複数の汎用レジスタを使用可能は機械で有効）

19 レジスタの使用について ① レジスタの個数には限り（8個、16個など）があるのでごく少数のデータしか保持できない。
② 主記憶装置よりレジスタのほうがアクセス速度が速い。 ③ 各種の演算では、オペランドの一方がレジスタ上になければならないケースがほとんどである。両方のオペランドが主記憶装置でもよいケースは少ない。 ■ 一時変数は記憶装置に割り当て、実行中にレジスタに移して使うのが基本。 ■ レジスタ割り当て（register allocation）は最適化として考える。

20 （４）フレーム ① コンパイラのオブジェクトは、機械語命令の部分とデータ部分に分かれる。
② プログラム単位ごとのデータ部分は、以下のように呼ばれる。 ■データフレーム（data frame） ■フレーム（frame） ■起動レコード（activation record） ■データセグメント（data segment）

21 フレーム内のデータ ① 原始プログラム内に現れる変数や定数のデータ ② コンパイラが生成する一時変数や作業用のデータ
③ 呼び出し側の復帰アドレス（return address） ④ 呼出し直前のレジスタの値（register save area） FORTRANではCOMMONフレームが別に存在する。 再帰的呼び出しが可能な言語では、 これらのデータをスタックに保持し、 リターン時に復帰する必要がある。

22 （５）再帰的呼び出しのフレーム内データ 再帰的呼び出しが可能な言語では、 フレーム内のデータを関数呼出しごとに スタックに保持し、
リターン時に復帰する必要がある。 【再帰的呼び出しの例】 fib(int n) { int m; if(n <= 2) m = 1; else m = fib(n - 2) + fib(n - 1); return m; }

23 再帰的呼び出しのスタック ① 関数呼出し直後のスタックトップには引数の個数分の呼出し時の実引数（評価済み）が格納されている。
① 関数呼出し直後のスタックトップには引数の個数分の呼出し時の実引数（評価済み）が格納されている。 ② 実引数をポップアップし、仮引数との対応付けを行う必要がある。この方法には、 　　　・ディープバインディング(Deep Binding) 　　　・シャドゥバインディング(Shadow Binding) がある（後述）。通常の言語では Deep Binding が使われるが、Lisp では Shadow Bindingが使われることが多い。 ③ 上記②のポップアップが行われた後、フレームの保存が行われる。

24 （６）ブロック構造 （a）Deep Bindingによる例
呼出しが A → B → C → B → D で 実行されたときのフレームのスタック Pascal Procedure A; Procedure B; Procedure C; begin ……… end; Procedure D; A 変数は、各フレームの相対番地（offset）で表現 B D B C 有効なフレーム

25 フレームのたどり方 A A B B D D B B C C 静的リンク（static link）法 ディスプレイ（display）法
（E.W.Dijkstra による） ディスプレイ A A B 1 B 2 D D 3 B B C C 有効なフレーム

26 （b）Shadow Binding （主としてインタプリタ言語で用いられる。例：LISP）
① 記号表を保持する。 ② 呼び出された関数の仮引数名やローカル変数を呼び出した関数の仮引数名やローカル変数を記号表に登録する（仮引数名の場合、引数を評価して値を設定する。参照渡しの場合は実引数の番地あるいは名前）。 ③ 同じ名前が記号表内にあっても重複登録する。 ④ 値を取り出したり、設定するときは記号表の最後から検索する（最も直近で登録された変数が有効となる）。 ⑤ 呼び出した関数に戻るとき、仮引数名やローカル変数を記号表から消す。

27 （７）ヒープ（heap）領域 ■文字列や配列など、不定長のデータに割り当てられる領域。 ■先に述べたごみ収集処理（GC処理）が必要となる。
■スタックと逆方向に使用領域を確保することが多い。