3番地コード

3番地コード（英: Three-address code）とは、コンパイラにおける中間言語の一種で、コンパイラ最適化の実装に使われる。2つの入力と1つの出力のアドレス（メモリまたはレジスタ）を指定する形式であるため、3番地コードと呼ばれる。

概要

3番地コードの各命令は、4-タプル（命令コード、オペランド1、オペランド2、結果）で表現される。これは、次のような一般形式で表される。

$x := y \, \operatorname{op} \, z\,$

ここで、x、y、z は変数や定数、あるいはコンパイラが生成した一時変数である。op は命令（コード）であり、算術演算に相当する。複数の演算で構成される次のような式があるとする。

$p := x + y \times z\,$

これをそのまま3番地コードの1命令で表現することはできない。そのため、次のような2つの命令に分解される。

$t_1 := y \times z\,$

$p := x + t_1\,$

オペランド数が違っていても「3番地コード」という呼び方をすることもある。3番地コードの本質は、各命令が正確に1つの基本的演算を実装している点であり、入出力オペランドには利用可能なレジスタが指定される。

3番地コードを改良したものを静的単一代入形 (SSA) と呼ぶ。

例

 int main(void)
 {
     int i;
     int b[10];
     for (i = 0; i < 10; ++i) {
         b[i] = i*i; 
     }
 }

上記のC言語プログラムを3番地コードに変換すると、次のようになる。

      i := 0                  ; 代入
L1:  if i < 10 goto L2       ; 条件付分岐
      goto L3                 ; 無条件分岐
L2:  t0 := i*i
     t1 := &b                ; 演算対象のアドレス
      t2 := i << 2            ; bは整数型配列なのでオフセットはi*4(=i<<2)バイト
      t3 := t1 + t2           ; t3 には b[i] のアドレスが設定される
      *t3 := t0               ; ポインタを通して格納する
      i := i + 1
      goto L1
L3:

関連項目

• 中間言語
• RISC

外部リンク

• Three-Address Code and Register Allocation
• CSc 453: A Three-Address Intermediate Code Instruction Set for C--