情報科学実験II資料 (7)
実マシンコード生成

田浦

26/11/98

実機械コード生成の概要

先週定義した抽象機械と実際の機械の間には, 機械ごとに大小様々な差がある. 各機械ごとに固有の事項は個々の機械ごとに必要なところを埋めてやるしかな いのでここでは詳しく述べないが, およそどんな機械であってもおこなわなく てはいけない話しは, データ表現の決定である. 実機械ではどんなデータも整 数として表さなくてはいけないので, 抽象機械レベルにおいてもなお, 「抽象 化」されていたデータ表現をここで, 具体的な整数値に置き換えてやる必要が ある.

Min-Scheme の1 wordは,

のいずれかを表し, 抽象機械では(1 Min-Scheme word = 2抽象機械wordを 仮定すると), のいずれかとなる.(注) 今回の資料では, 以下単にwordといった時には, 抽象機械wordまたは実機械 wordのことを指し, Min-Scheme 1 wordは機械の2 word に対応するものとす る. さて, 次の二つの理由から, これらを実行時に区別できなくてはいけない. 実際にはどちらもレイトレだけを動かすためにはなしですませられるものだが, (注) ここでは 一般的な, 各下位word中の各2 bitをtagとして用いる方式を紹介する. つまり ここでは浮動小数点を表すのに30 bitしか使えない(2 bit削っても精度的には OKと仮定する. ルール違反ではないでしょう)とする. 上位wordについては tagはつけなくて良い.

Tagging Scheme

Tagging Schemeは, あるデータの論理的な値(つまり抽象機械における値)が与 えられた時に, それをどのような整数で表すか, を計算する関数Tを与える ことによって表現される. 実際のtaggingはかなり任意性のあるもので各種制 約に応じて決めるのが良い. ここでは例として以下のようにする.

整数
T (i) = 4 i + 1 つまり整数の下位2 bitは01.
ポインタ
T (a) = a - 1 (ただし, aが実際にデータが割り当て られているアドレスで, それは4の倍数と仮定する.) つまりポインタの下位2 bitは11.
浮動小数点数
30 bitの表現を, h: 上位16 bit, l: 下位14 bit として, それぞれのbit表現を整数だと思った時に
その他
ここまでで, 下位2 bitは, 01, 11, 00が使われている ので, 残る10を用いて, さらにtagをつけて, 論理値(2通り), 文字(256 通り), 空リスト(1通り)をencodeすれば良い(省略).

上位wordにはtagがついていないので, たとえばメモリ中のあるwordに, 0001000100110011というデータが格納されていた時, それが何か浮動小数点の 上位wordなのか, それともアドレス0001000100110100を指すポインタなのかを 別の方法で区別できなくてはならない. その仕掛けは, .

各種演算の実現

各種演算を実現するには, データの表現を考慮して, tagをはずした元のデー タを求めて, 実際に演算をして, 再びtagのついたデータを構築する必要があ るが, 実際にはこれらのstepは, 実際に実行時にtagをつけたり外したりしな くても1度にできることが多い. すべてではないが重要なものを見ていく. 一 般には, 抽象機械での演算:

(op x y r)
を実現するためには,
r := T(T-1(x) op T-1(y))
を計算してやれば良い.

足し算

(+ x y r)
において, x, yは整数だから, T-1(x)=(x-1)/4 . したがって,
r := 4((x - 1)/4 + (y - 1)/4) + 1 = x + y - 1
したがって単に与えられたデータ表現に対して実機械における足し算を実行し, 1を引けば良い. 特にどちらかが定数の時はオーバーヘッドなしで実行できる.

引き算

(- x y r)
は,
r := 4((x - 1)/4 - (y - 1)4) + 1 = x - y + 1

メモリ参照

ここが少しだけ注意が必要である.

(rrefl p i r)
(rrefh p i r)
の2種類の抽象機械命令があるものと仮定する. (rrefl p i r)は, レコードpi Min-Scheme word目の下位wordを読んでレジス タrに格納する命令, (rrefh p i r)はレコードpi Min-Scheme word目の上位wordを読んでレジスタrに格納する命令である (つまり, CPSの1 rref命令は一般には抽象機械の2 rref命令に変 換される. (注)).

注意としては, iはMin-Scheme の1 word, つまり抽象機械の2 wordを単位 としてaddressingされていることで, そのことを考慮して実際にアクセスすべ きアドレスを求める. ここで典型的な場合として, 実機械のaddressingの単位 を8 bitとする(つまり, アドレスaa+1の間に8 bit入っている)と, アク セスしたいアドレスは, rreflの場合,

al = T-1(p) + 4T-1(i)
で, rrefhの場合,
ah = T-1(p) + 4T-1(i) + 2
であり, それぞれ,
al = p + 1 + 4((i - 1)/4) = p + i,
ah = p + 1 + 4((i - 1)/4) + 2 = p + i + 2
となる.

このtag付けのtrickyなところは, 整数の下2 bitがあらかじめtagとなってい るために, それが結果的にwordサイズに合わせてオフセットをスケーリングし たことになっている. また, メモリアクセス命令として, レジスタオフセット をサポートする場合に, 2種類(素直に足し算したアドレスをアクセスするもの と, そのアドレスのさらに2 byte先をアクセスするもの)を用意しておくと便 利ではある.

その他の命令に関しても同様に, 各命令の引数の型に応じて, 結果を計算する 実機械命令を生成できる.

オブジェクトコードの生成

今までの話しで, Min-Scheme の関数定義を受けとり, それをCPSに変換し, closure変換を行ない, 抽象機械コードを生成し, 実マシンコードを生成でき るようになった.

実際のcompileの単位は, toplevel定義の羅列である. そ こには,

(define (f x)
  (+ x 1))
のように, 関数を定義するものと,
(define y (g 10))
のように, それ以外の値も定義できるものとがある. 特にMin-Scheme におい てはfix式が許されないからこの二つの区別は厳格である. (注)

Compiler作りの最後の仕上げとしてこの羅列を受けとり, そこからオブジェク トコード(unixの.oに相当するもの)を出すことを, 今一度整理してみる. つまりcompileというものが受けとるもの, 出力するものを整理してみる. 例 えば, 特にオブジェクトコードはただの実マシンコードの羅列だけでは 済まないのは明らかである. 例えば,

(define y (g 10))
に対してはどこかのアドレスに(g 10)を実行した値が書かれていて, 他 の(現在のcompilation unit内ではないかも知れない) 場所からyを参照 したらそのアドレスを読むようになっていなくてはならないはずである. さら にyを初期化するに当たっては一般には何らかのコード(この場合は, (g 10))を実行しなくてはならないはずである. それらはSchemeのmain 関数の前に実行されねばならない.(注)

一般には,

オブジェクトコード
= Toplevelのsymbolの値を格納するためのデータ領域 (初期化デー タ領域)
+ 決められたエントリポイントが呼び出されるとそれらを初期化するような コード (初期化コード)
という見方をすれば良い.

例えば,

(define (f x) (+ x 1))

(define (g x) (+ (f x) 1))

(define y (g 10))
というcompilation unitにおいては, になる.

それぞれを生成し, それをひっつけたものが出力結果, それをfileに書いて, どこからどこまでが初期化データ領域で, 初期化コードはどこから始まるみた いなことをfileに書けば, いわゆる.oに相当するものになる. (注)

初期化データ領域は単に, 定義されたsymbolの数だけ確保すれば良いから, 後 は, 初期化コードをいかに楽して出すかを考える.

初期化コード

初期化コードを生成するのに, 直接マシンコード生成をしようなどと考える必 要はない. CPSレベルで容易に実現できる.

最初の例に戻ると,

(define (f x) (+ x 1))

(define (g x) (+ (f x) 1))

(define y (g 10))
このcompilation unitを初期化するコードは以下のようなCPS関数として実現 できる.
(init-module (c0) 
  (fixh ((f (k1 x) (+-two (x 1) (v2) ((appb k1 (v2)))))) 
    (rset! ((label f) 0 f) () 
      ((fixh ((g (k3 x) (fixs ((k5 (r6) (+-two (r6 1) (v4) 
                                          ((appb k3 (v4)))))) 
                          (appf f (k5 x))))) 
         (rset! ((label g) 0 g) () 
           ((fixs ((k7 (r8) (rset! ((label y) 0 r8) () ((appb c0 (#t)))))) 
              (appf g (k7 10))))))))))
init-moduleを普通の関数同様, 適当なc0(FIXSで割り当てられた 継続)を与えて呼び出してやると, (label f), (label g), (label y)を それぞれ適切に初期化した上で返ってきてくれる. プログラムの初期化時にす べてのmoduleのinitializeルーチンを呼んでやれば, main関数の実行準備が整っ たことになる.

やっていることは,

一般的な枠組を示すと,

後はこの関数に対して, 今まで述べた要領でコードを生成すれば, 自動的にそ れがそのcompilation unitに対するコード領域のイメージになる.

Min-Scheme の場合の注意

なお, 上で生成されるCPSコードはnestしたFIXHを使っているため, 一見 Min-SchemeFix だけに通用する考え方であるように見えるが, 実際には定義さ れる各関数は自由変数を持たないから, Min-SchemeFix にあったようなFIXHに 対する一般的なclosure変換関数などを実装する必要はない.(注) 実際, closure変換を行なうと, 各 toplevel関数に対するclosureは, コード番地のみを含む1 wordのclosureにな るはずであるから, そのようなコードを最初から生成するclosure変換もどき を付け焼き場的に作ってしまえば良い. つまり, init-moduleのコードを

(init-module (c0) 
  (heap ((label f:)) (f) 
    (rset! ((label f) 0 f) () 
      (heap ((label g:)) (g)
        (rset! ((label g) 0 g) () 
          ((fixs ((k7 (r8) (rset! ((label y) 0 r8) () ((appb c0 (#t)))))) 
             (appf g (k7 10)))))))))
のように変換してやれば, それはclosure変換をしたのと同じことになる. ここで,
(heap ((label f:)) (f)
などによりf, gを作っているが, これは実際にclosure formatを 計算して求めているのではなく, fgが実際には自由変数 を含まないという知識を利用して, 最初からそう決めつけてしまっているだけ である.

なお, (fixなしの)Min-Scheme に対しては各toplevel関数に対するclosureを 作る必要はない. 上ではあえてそのようにしてあるが, その章に述べてあるこ とを採用するのであれば,

(heap ((label f:)) (f) 
  ((rset! ((label f) 0 f) ()
によって, fのclosure recordを作る変わりに, 単に,
(rset! ((label f) 0 (label f:)) ()
としてしまえば良い.

Linkerの仕事

さて, 抽象機械コードおよび(おそらく)実マシンコードには, 命令のオペラン ドとして, labelなるものをとることができたが, それは最終的に全てのモジュー ルをlinkする時に, 適切なアドレス定数にsubstiteされる.

各オブジェクトコードは, link用に以下のような情報を用意する.

外部から参照可能なlabelの名前とは, 一般的にはtoplevelで定義された symbolということになる. これをglobalなlabelと呼ぶことにする.

Linkerは与えられた全てのオブジェクトファイルの初期化データ領域および初 期化コードをつなぎ合わせた時に, 各外部ラベルの値(アドレス)を求め, それ を利用してlabelの使用場所をそのアドレスで置き換える.

また, 初期化コードを順に呼んだのちに, main関数を呼ぶようなコードを生成 そのコードの先頭をプログラムのentry pointとする.

Linkerが必要な理由はcompilation unit中に外部参照が含まれていても compileを行なえるようにするため(つまり分割compileをsupportするため)で あり, オブジェクトファイルがbinary fileである必要性は(link時間を短くす る理由以外には)ない. Binary fileをいじるのが面倒であれば, オブジェクト ファイル= assembly textとしてしまって, リンクはすべてのassembly text をつなげて, assembleするだけでも良い(もちろんアセンブラがラベルの使用 を許しているというのが前提).


...のいずれかとなる.
浮動小数点以外は, 片方のwordにしか意味がな い.
...実際にはどちらもレイトレだけを動かすためにはなしですませられるものだが,
注: レイトレがnull?などを使わないという意味ではない. 使 われてはいるが, そこでは空リストと, 空でないリストだけが区別できれば良 いのであって, その他のすべてのデータ(たとえば整数)と厳密に区別できな ければいけないわけではない, という意味である. 詳しくは後述.
...換される.
レジスタ割り当て時の簡単な工夫で多くの場合, それが避けられる ことを資料(6)で述べた.
...てはfix式が許されないからこの二つの区別は厳格である.
Min-Scheme11#11 においては, (define (f x) ...)は, (define f (fix ((t (x) ...)) t))のことだと思えるのでこの二つを区 別する必然性に乏しいが, 以下ではfix式が存在しなくても通用するよ う, 二つを区別して考える.
...関数の前に実行されねばならない.
Cなどではそれをしなくてもいい ように, 初期化式に書ける式が制限されている. C++ではコンストラクタが main関数に入る前に呼ばれるようにするために, リンカが苦労している.
...いわゆる.oに相当するものになる.
しかし我々のつくっているものは, 任意の複雑な初期化式を許すか ら, unitxの.oよりも立派である.
...対する一般的なclosure変換関数などを実装する必要はない.
そうし ても実際には対した手間ではないが.
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999