IoPLMaterials

Edit this page Report an issue

アセンブリ生成

この節では，前の節の説明に従って生成した仮想マシンコードを入力とし，現実の計算機アーキテクチャの一つであるMIPSのアセンブリコードを生成する方法について説明する．説明にあたり，MIPSに関する基本的な知識は仮定する．

MIPS の呼出し規約

（本節は一部MIPSアセンブリ言語入門と重複する．）

現実のハードウェアが備えている物理レジスタの個数は有限である．そのため，関数（とくに再帰関数）を用いるプログラムではプログラム中のすべての計算を物理レジスタだけで実行することは困難であり，一般に，何らかの方法に則ってプログラム中の各変数の値を格納する場所をメモリ中のどこかへ確保する必要がある．

たとえば，次のようなMiniML4のプログラム（を読みやすさのためにMiniML4のシンタックスではなく同等の言語機能によるOCamlのシンタックスを使って説明したプログラム）

let rec f a = a + 1
and g b = f b
in g 0

を素朴に実行するだけであれば，プログラム全体で，「関数fの引数aを格納する場所」「関数fを呼び出した結果（返り値）を格納する場所」「関数gの引数bを格納する場所」「関数gの返り値を格納する場所」の計4ワード分を確保すれば十分である．

しかし，そのような素朴な方法だと，たとえば：

let rec fact = fun n -> if n > 0 then n * fact (n + (-1)) else 1
in fact 10

のような再帰関数factにおいては，複数の異なる(再帰)呼出しの引数や返り値の格納場所が同じ領域を使うことになり，実行がおかしくなってしまう．具体的には，関数呼出しfact 9の直後には，その返り値に対し$10$を掛ける必要があるが，関数呼出しfact 10の引数である値$10$は，factの引数を格納するただ一つの場所に置かれていたため，すでに値$9$で上書きされ失われてしまっている（正確には，さらに$8, 7,\ldots,0$で上書きされているが，ともかく$10$という値はもはや存在しない）．

結局のところ，関数定義単位で必要な領域のサイズを求め，その総和分を確保するだけでは不十分であり，関数呼出し毎に異なる場所を確保する必要があることが分かる．そこで，関数機能を持つプログラミング言語（関数型言語に限らず，たとえばC言語なども含む）の処理系では，通常，呼出し/リターンの制御構造に対応できるよう，各関数呼出しの実行に必要となるメモリ領域を管理するためのデータ構造として，LIFO (last-in first-out)で管理するスタックを用いる．また，このスタックは，呼出し側が関数呼出しの次に実行するべき命令のアドレス（リターンアドレス (return address)と呼ばれる）を保存しておくためにも用いられる（詳細は後述）．

原理的には，ここまでに説明したように各関数の実行で必要となるすべての引数・返り値・局所変数（ならびにリターンアドレス）のための場所をスタック上に必ず確保することにすれば，再帰関数を含むようなプログラムであっても正しく実行できるが，それだけだと，プログラム実行中に計算されるすべての値をメモリ領域にいちいち格納するため，レジスタを有効活用できておらず実行性能はあまり良くない．たとえば，返り値を格納する場所をスタック上のある場所に定めてしまうと，（とくにレジスタで計算を行うRISC系のハードウェアにおいては）呼び出された側が最後にスタックのその場所に返り値をストアしたすぐ後に，呼出し側が同じ場所からレジスタへロードするということが頻繁に起こる．この実行オーバヘッドは，たとえば「関数呼出しの返り値は必ずv0レジスタを使って受け渡しする」と決めておけば避けることができる．まったく同様に，引数の受け渡しについてもレジスタの使い方に関し何らかの約束事を決めておけば，実行効率を良くすることができる．

以上のようなスタックとレジスタの使い方に関する約束事は，レジスタの種類や個数，関数の呼出し/リターンに用いることのできるジャンプ命令の詳細な振舞いなどに依存するため，通常，計算機アーキテクチャ毎に定められている．関数呼出しに関するそのような約束事は，一般に呼出し規約 (calling convention)と呼ばれる．

なお，本講義で作成するMiniML4-コンパイラはMIPSアセンブリをターゲットとしているため，本来であればMIPSの呼出し規約に厳密に従うべきところだが，説明を簡単にするため，少し簡略化した独自の呼出し規約を用いている．より本格的なプログラミング言語や言語処理系との互換性を気にする場合には，この資料に書かれている説明を理解した後に各自でさらに勉強して欲しい（「MIPS calling convention」などと検索すれば，たくさんの情報を得られる）．

MiniML4-コンパイラにおける呼出し規約

まず，関数の返り値については先程触れたように，v0レジスタを介して受け渡すことにする．また，MiniML4-言語におけるすべての関数は引数を1つしか受け取らないため，その唯一の引数はa0レジスタを介して受け渡すことにする．

各関数を実行するために必要なスタック上の連続領域（フレーム (frame)と呼ぶ）は，以下の図に示すように，スタックの一番上（メモリアドレスは下位の方）に確保される．

上位アドレス
               |             |
               | ...         |
               +-------------+         
               | ra          |        |
               | saved a0    |        | スタックの伸びる向き
               | local 4n    |        V
               | ...         |
               | local 4     |
               | local 0     |<- $sp
               +-------------+
下位アドレス

フレーム中に含まれる各データの説明は以下のとおりである．

なお，spレジスタ（スタックポインタ）は，常にスタック最上部（フレームの一番下）を指すようにする．したがって，$i$番目 $(1 \le i \le N)$ の局所変数が格納されている領域はアドレス$sp + 4iとなる．また，saved a0 のアドレスは$sp + 4N + 4，リターンアドレスのアドレスは$sp + 4N + 8となる．

以下は，上記のスタックレイアウトに基づいて関数呼出しを行う手順の概要である（詳細な手順については次節を参照）．

最後に，以下の簡単なOCamlコード：

let rec f a = g (a+1)
and g b = let x = b + b in
          let y = x * x in
          let z = y - 1 in
            z
in f 0

の実行中，関数fから関数gを呼び出す前後のスタックの状態を以下に示す．

関数gを呼び出す直前

      +-------------+
   |  | saved a0: - |
   |  |   ...       |
   V  | [f's frame] |
      |   ...       |<- $sp
      +-------------+







         $a0 = 0

g を呼び出した直後

      +-------------+
   |  | saved a0: 0 |
   |  |   ...       |
   V  | [f's frame] |
      |   ...       |
      +-------------+
      |     ra      |
      | saved a0: - |
      |     z: -    |
      |     y: -    |
      |     x: -    |<- $sp
      +-------------+

        $a0 = 1

g からのリターン直後

      +-------------+
   |  | saved a0: 0 |
   |  |   ...       |
   V  | [f's frame] |
      |   ...       |<- $sp
      +-------------+
  
  
  

  
  

         $a0 = 0
         $v0 = 3

現実の呼出し規約に関する余談

一般のプログラミング言語では，多引数関数を定義できたり，引数の数が固定ではない（可変長引数と呼ばれる）関数を定義できたりする．また，関数本体の実行中に使用するメモリサイズを正確に求めることが難しいこともある（たとえば，スタック上に任意サイズのメモリ領域を確保できるC言語のalloca関数を使用した場合など）．そのような場合，物理レジスタに収まりきらない引数をスタックに置く必要がある．それに加え，実行中に位置が一定ではないspレジスタからの相対アドレスを用いてスタック中のパラメータおよび局所変数へアクセスしようとすると，コンパイル時に求める必要のある相対アドレスの計算が複雑になる．

そこで，現実のコンパイラにおいては，spレジスタとは別に，関数フレームのspとは反対側（典型的にはraの入っているあたり）を常に指し続けるfpレジスタを別に用意しておき，パラメータや局所変数へのアクセスにはfpレジスタからの相対アドレスを用いるのが一般的である．ただし，リターンアドレスと同様に，呼出し側のfpレジスタの値もスタック中に退避する手間がさらに必要となる．

アセンブリ生成

以上を踏まえて，$\mathcal{V}$のプログラムをMIPSアセンブリに変換する関数$\mathcal{G}$の定義を示す．

オペランドの変換

オペランドの変換$\mathcal{G}_{r}(\mathit{oprd})$は以下の通りである．

\[\begin{array}{rcl} \mathcal{G}_{r}(\mathbf{param}(1)) &=& \begin{array}[t]{ll} \texttt{move} & r,\mathtt{\$a0}\\ \end{array}\\ \mathcal{G}_{r}(\mathbf{local}(n)) &=& \begin{array}[t]{l} \texttt{lw} & r,n(\mathtt{\$sp})\\ \end{array}\\ \mathcal{G}_{r}(\mathbf{labimm}(l)) &=& \begin{array}[t]{l} \texttt{la} & r,l\\ \end{array}\\ \mathcal{G}_{r}(\mathbf{imm}(n)) &=& \begin{array}[t]{l} \texttt{li} & r,n\\ \end{array}\\ \end{array}\]

オペランドの変換は$\mathcal{G}_{r}(\mathit{oprd})$で行う．この変換では「$\mathit{oprd}$に格納されている値をレジスタ$r$にロードする」MIPSアセンブリが生成される．各ケースの説明は以下の通りである．

命令の変換

命令の変換を行う関数$\mathcal{G}_{n}(i)$は，$\mathcal{V}$の命令$i$を，局所変数用に$n$バイトを使う関数の内部にあると仮定して実行するMIPSの命令列を生成する．この$n$はフレーム内に格納されている値にアクセスする際に，そのアドレスの$\mathtt{$sp}$からのオフセットを計算するために用いられる．定義は以下の通りである．

\[\begin{array}{rcl} \mathcal{G}_{n}(\mathbf{local}(\mathit{ofs}) \leftarrow \mathit{oprd}) &=& \begin{array}[t]{l} \mathcal{G}_{\mathtt{\$t0}}(\mathit{oprd})\\ \mathtt{sw} \quad \mathtt{\$t0}, \mathit{ofs}(\mathtt{\$sp})\\ \end{array}\\ \mathcal{G}_{n}(\mathbf{local}(\mathit{ofs}) \leftarrow \mathit{bop} \; \mathit{oprd}_1,\mathit{oprd}_2) &=& \begin{array}[t]{l} \mathcal{G}_{\mathtt{\$t0}}(\mathit{oprd}_1)\\ \mathcal{G}_{\mathtt{\$t1}}(\mathit{oprd}_2)\\ [\![\mathit{bop}]\!] \quad \mathtt{\$t0}, \mathtt{\$t0}, \mathtt{\$t1}\\ \mathtt{sw} \quad \mathtt{\$t0},\mathit{ofs}(\mathtt{\$sp})\\ \end{array}\\ \mathcal{G}_{n}(l:) &=& \begin{array}[t]{l} l: \end{array}\\ \mathcal{G}_{n}(\mathbf{if} \; \mathit{oprd} \ne 0 \; \mathbf{then} \; \mathbf{goto} \; l) &=& \begin{array}[t]{l} \mathcal{G}_{\mathtt{\$t0}}(\mathit{oprd})\\ \mathtt{bgtz} \quad \mathtt{\$t0},l\\ \end{array}\\ \mathcal{G}_{n}(\mathbf{goto} \; l) &=& \begin{array}[t]{l} \mathtt{j} \quad l \end{array}\\ \mathcal{G}_{n}(\mathbf{local}(\mathit{ofs}) \leftarrow \mathit{oprd}_f(\mathit{oprd}_1)) &=& \begin{array}[t]{l} \mathit{Save}_{n+4}(\mathtt{\$a0})\\ \mathcal{G}_{\mathtt{\$a0}}(\mathit{oprd}_1)\\ \mathcal{G}_{\mathtt{\$t0}}(\mathit{oprd}_f)\\ \mathtt{jalr} \quad \mathtt{\$ra},\mathtt{\$t0}\\ \mathtt{sw} \quad \mathtt{\$v0},\mathit{ofs}(\mathtt{\$sp})\\ \mathit{Restore}_{n+4}(\mathtt{\$a0})\\ \end{array}\\ \mathcal{G}_{n}(\mathbf{return} \; \mathit{oprd}) &=& \begin{array}[t]{l} \mathcal{G}_{\mathtt{\$v0}}(\mathit{oprd})\\ \mathit{Epilogue}(n)\\ \mathtt{jr} \quad \mathtt{\$ra}\\ \end{array}\\ \end{array}\]

各ケースの説明は以下の通りである．

上述の$\mathit{Save}$と$\mathit{Restore}$は以下のように定義すればよい．

\[\begin{array}{l} \begin{array}{rcl} \mathit{Save}_n(r) &=& \begin{array}[t]{l} \mathtt{sw} \quad r,n(\mathtt{\$sp}) \end{array}\\ \end{array}\\ \begin{array}{rcl} \mathit{Restore}_n(r) &=& \begin{array}[t]{l} \texttt{lw} \quad r,n(\mathtt{\$sp}) \end{array}\\ \end{array} \end{array}\]

また，$\mathit{Epilogue}$の定義は以下の通りとなる．

\[\begin{array}{rcl} \mathit{Epilogue}(n) &=& \begin{array}[t]{l} \mathit{Restore}_{n+8}(\mathtt{\$ra})\\ \mathtt{addiu} \quad \mathtt{\$sp},\mathtt{\$sp},n+8\\ \end{array}\\ \end{array}\]

関数定義の変換

関数定義

\[d := \left(\begin{array}{l} l:\\ \; i_1\\ \; \dots\\ \; i_m\\ \end{array}, n\right)\]

に対応する命令列$\mathcal{G}(d)$は以下のとおりとなる．

\[\begin{array}[t]{l} l\mathtt{:}\\ \; \mathit{Prologue}(n)\\ \; \mathcal{G}_{n}(i_1)\\ \; \dots\\ \; \mathcal{G}_{n}(i_m)\\ \end{array}\]

定義を以下に説明する．

$\mathit{Prologue}$の定義は以下の通りである．

\[\begin{array}{rcl} \mathit{Prologue}(n) &=& \begin{array}[t]{l} \mathtt{addiu} \quad \mathtt{\$sp},\mathtt{\$sp},-n-8\\ \mathit{Save}_{n+8}(\mathtt{\$ra})\\ \end{array}\\ \end{array}\]

プログラムの変換

最後に，プログラム

\[\left( \begin{array}{l} d_1\\ \dots\\ d_m\\ \mathit{main}:\\ \; i_1\\ \; \dots\\ \; i_n\\ \end{array}, k \right)\]

に対応するアセンブリは以下の通りとなる．

\[\begin{array}[t]{l} \mathtt{.text}\\ \mathtt{.globl\ main}\\ \mathcal{G}(d_1)\\ \dots\\ \mathcal{G}(d_m)\\ \mathtt{main:}\\ \; \mathit{Prologue}(k)\\ \; \mathcal{G}_k(i_1)\\ \; \dots\\ \; \mathcal{G}_k(i_n)\\ \end{array}\\\]

まず先頭で，以降にかかれている情報がプログラムである旨を示す$\mathtt{.text}$ディレクティブを生成している．その次の行には，アセンブリ中の$\mathtt{main}$というラベル名がグローバルなラベル，すなわち外部から見える名前であることが宣言されている．その後$d_1$から$d_m$までのアセンブリを順番に生成した後に，$\mathtt{main:}$に続いて，メインのプログラムを実行するためのフレームの確保を$\mathit{Prologue}(k)$で行い ($k$はフレームのサイズ)，命令列$i_1 \dots i_n$に対応するアセンブリを生成する．