LIRの仕様

- 概要
- 設計目標
- 実現方針
- 他の中間言語との比較
- 構文と意味
- LIRの読み方
- 詳細仕様

### 4.1. 低水準中間表現LIRの概要

低水準中間表現には、多くの機種に適用できるばかりでなく、機械語のレベルでの最適化処理も表現できることが要求される。

初期のコンピュータのアーキテクチャは多種多様であったが、現在使われているコンピュータ、あるいは近い将来出現すると予測されるコンピュータは、２進数表現、２の累乗のビット数の語長、整数と浮動小数によるデータ表現など、共通した機構に基づいている。効率のよいコードを生成するにはレジスタを効率よく使わなくてはならないので、スタックマシンではなく、レジスタマシンを抽象化したものとすべきである。

このような考察に基づいて設定した中間表現が本コンパイラ・インフラストラクチャの低水準中間表現LIR (Low-level Intermediate Representation)である。

LIRは、次のような点を特徴としている。

- バックエンドにおける変換過程で、具体的オペレータ等は対象機種の機械語に近づいてゆくが、LIRの文法はバックエンドの全フェーズを通じて共通なので、LIRに対する処理を機種に依存しない形で作成できる。
- それを利用して、リターゲット型のコード生成系を実現している。
- 抽象レジスタマシンに対する完全なアセンブリ言語の形態をとり、テキスト表現で入力したLIRに基づいて、フロントエンドと切り離した形でもコード生成ができる。
- 意味仕様が表示的意味論で厳密に定義されており、曖昧性がない。

### 4.2. LIRの設計目標

LIR の設計目標は以下の通りである。

1. バックエンドの全フェーズを通じて使用できる中間言語
2. １つの独立したプログラミング言語であること
3. バックエンドのユーザにとって使いやすい中間言語

コード最適化からアセンブリ言語出力までが、単一の中間言語で表現されること(目標 1.)により、LIR を操作する手続きの共通化が図れる、これはバックエンドのユーザにとっても好ましい(目標 3.)。

従来、コンパイラの中間言語はコンパイラ作成者のみ知り得るものでよく、また四つ組、木構造、あるいは疑似アセンブラ、等で表現された式の列のみを中間言語と呼んでいた。しかし実際には式の列のみでは、独立したプログラムにはならない。それらの式から参照されている変数、関数としてのインタフェース、モジュール構造といった上位構造が欠けているからである。従来のコンパイラにおいても、それら上位構造 はもちろん表現されているが、それは暗黙的であり、通常中間言語の一部とは見なされていなかった。LIR ではそれらの上位構造も含めて中間言語と考える。

これにより、バックエンドの各フェーズは厳密に LIR の変換プログラムとしてとらえることが可能となる。あるフェーズ間を渡される LIR プログラムは単なるデバッグダンプではなく、単独で意味を持つ変換途中のプログラムであり、各フェーズの実装とは完全に独立しているので、バグの発見を含めた解析も容易になる(目標 3.)。

### 4.3. LIRの実現方針

LIR の実現方針は以下の通りである。

1. 式は木構造で表現する
2. S-式ベースの構文を持つ、プログラミング言語として設計する
3. 型は通常の計算機が扱える低レベルのものに限定する
4. 高級言語と同様に、意味の定義も可能な限り厳密に行う。

汎用性や命令選択の都合を考慮し、式は木構造で表現する(方針 1.)。

また構文的な扱いを容易にするために、S-式ベースの構文を採用する(方針 2.)。

さまざまな高級言語の型に依存するような最適化、プログラム変換は HIR で行われる。LIR はソース言語に依存しないコード最適化及びコード生成で使われる言語であるから、型としては低レベルのものに限定する(方針 3.)。

厳密な意味定義(方針 4.)はリターゲッタブル性を考慮した中間言語において本質的であり、Java で実装されている COINS コンパイラは本質的にクロスコンパイラであるから、この方針は実質的にも意味がある。

### 4.4. 他の中間言語との比較

LIR と類似な中間言語には、gcc の RTL 及び Haskell プロジェクトの C-- がある。

gcc の RTL は S-式表現を持つ点など、LIR と似ているが、RTL は上でいう上位構造を持たず、独立した言語として定義されてはいない。デバッグダンプとして RTL を表示することは可能だが、それを入力としてあるバックエンドパスを実行することは不可能である。

C-- は主に関数型言語の実装を目的として設計された(高級な)中間言語である。関数や変数の定義が可能であるという点で似ているが、命令選択やレジスタアロケーションもこの言語の上で行うことは考えていない。むしろ C-- は関数型言語の実装に不要なものを削除し、必要なものを導入したような C 言語であり、その意図は我々の LIR とは異なる。

### 4.5. LIRの構文と意味

バックエンドはL-moduleと呼ばれるコンパイル単位を読み、これをコンパイルする。L-moduleは いくつかのL-functionを含む。L-functionはL式の列を含む。それらの構文は以下のとおりである。

    L-moduleの構文定義

    <Lmod>          ::= (MODULE <Name> <GlobalSymtab> { <Ldata> | <Lfunc> })
    <Name>          ::= <QuotedString>
    <GlobalSymtab>  ::= (SYMTAB { <StaticSymbol> | <RegSymbol> })

    <StaticSymbol>  ::= (<Name> STATIC <Ltype> <Align> <Segment> <Linkage>)
    <RegSymbol>     ::= (<Name> REG    <Ltype> <Align> <Offset>)
    <FrameSymbol>   ::= (<Name> FRAME  <Ltype> <Align> <Offset>)
    <Align>         ::= <Fixnum>
    <Offset>        ::= <Fixnum>
    <Segment>       ::= <QuotedString>
    <Linkage>       ::= LDEF | XDEF | XREF

    <Ldata>         ::= (DATA <Name> { <DataSeq> | <ZeroSeq> | <SpaceSeq> })
    <DataSeq>       ::= (<Ltype> { <Fixnum> | <Flonum> | <Lexp> })
    <ZeroSeq>       ::= (ZEROS <Fixnum>)
    <SpaceSeq>      ::= (SPACE <Fixnum>)

    <Lfunc>         ::= (FUNCTION <Name> <LocalSymtab> <Lseq>)
    <LocalSymtab>   ::= (SYMTAB { <FrameSymbol> | <RegSymbol> })
    <Lseq>          ::= { <Lexp> }

    L式の構文定義

    <Lexp>         ::= <TypedExp> | <UntypedExp>

    <TypedExp>     ::= <AtomicTypedExp> | <NonAtomicTypedExp>
    <AtomicTypedExp> ::= <ConstExp> | <AddrExp> | <RegExp>
    <NonAtomixTypedExp> ::= <PureExp> | <MemExp> | <SetExp>
    <UntypedExp>   ::= <JumpExp> | <DefLabelExp> | <CallExp>
                     | <InterfaceExp> | <SpecialExp> | <LineExp>
    <Ltype>        ::= <Itype> | <Ftype> | <Atype>
    <Itype>        ::= I8 | I16 | I32 | I64 | I128
    <Ftype>        ::= F32 | F64 | F128
    <Atype>        ::= A<Fixnum>

    <ConstExp>     ::= (INTCONST <Itype> <Fixnum>)
                     | (FLOATCONST <Ftype> <Flonum>)

    <AddrExp>      ::= <StaticExp> | <FrameExp> | <LabelExp>
    <StaticExp>    ::= (STATIC <Ltype> <name>)
    <FrameExp>     ::= (FRAME <Ltype> <name>)
    <LabelExp>     ::= (LABEL <Ltype> <name>)

    <RegExp>       ::= <SimpleRegExp> | <SubregExp>

    <SimpleRegExp> ::= (REG <Ltype> <name>)
    <SubregExp>    ::= (SUBREG <Ltype> <SimpleRegExp> <Fixnum>)
    <PureExp>      ::= (<PureOp> <Ltype> <TypedExp> { <TypedExp> })

    <PureOp>       ::= NEG | ADD | SUB | MUL | DIVS | DIVU | MODS | MODU
                     | BAND | BOR | BXOR | BNOT
                     | LSHS | LSHU | RSHS | RSHU
                     | CONVSX | CONVZX | CONVIT
                     | CONVFX | CONVFT | CONVFI | CONVSF | CONVUF
                     | TSTEQ | TSTNE | TSTLTS | TSTLES | TSTGTS
                     | TSTGES | TSTLTU | TSTLEU | TSTGTU | TSTGEU

    <MemExp>       ::= (MEM <Ltype> <TypedExp> [&<MemModifier>])
    <MemModifier>  ::= V | N
    <SetExp>       ::= (SET <Ltype> <LvalueExp> <TypedExp>)
    <LvalueExp>    ::= <MemExp> | <RegExp>
    <JumpExp>      ::= (JUMP <LabelExp>)
                     | (JUMPC <TypedExp> <LabelExp> <LabelExp>)
                     | (JUMPN <TypedExp> ( { (<Fixnum> <LabelExp>) } ))

    <DefLabelExp>  ::= (DEFLABEL <label>)
    <label>        ::= <QuotedString>

    <CallExp>      ::= (CALL <Callee> <Arguments> <Receivers>)
    <Arguments>    ::= ( { <TypedExp> } )
    <Receivers>    ::= ( { <LvalueExp> } )

    <InterfaceExp> ::= <PrologueExp> | <EpilogueExp>
    <PrologueExp>  ::= (PROLOGUE (<Fixnum> <Fixnum>) { <LvalueExp> })
    <EpilogueExp>  ::= (EPILOGUE (<Fixnum> <Fixnum>) { <TypedExp> })

    <SpecialExp>   ::= <ParallelExp> | <UseExp> | <ClobberExp>
    <ParallelExp>  ::= (PARALLEL { <SetExp> | <CallExp> | <UseExp> | <ClobberExp> })
    <UseExp>       ::= (USE { <RegExp> })
    <ClobberExp>   ::= (CLOBBER { <RegExp> })

    <LineExp>      ::= (LINE <Fixnum>)

図4-１　LIRの構文

#### L式のセマンティックス

##### Const式

ここではConst式に対する意味を定義する。ASMCONST式はPure式に分類されている。

(INTCONST t z)  t∈Itype
  z∈Zを型tで表した整数値を表す。
(FLOATCONST t r)  t∈Ftype
  r∈Rを型tで表した浮動小数値を表す。

##### Addr式

ここではAddr式の意味を定義する。Static式はグローバル変数のアドレス、Frame式はローカル変数のアドレスを表すためのものである。Label式はL関数のロケーションを表す。

(STATIC t s)  t∈Itype
  s∈Stringで示されるプログラムメモリまたはデータメモリのアドレス。
(FRAME t s)  t∈Itype
  s∈Stringで示されるオフセットとフレームポインタの和で生成されるデータメモリのアドレス。
(LABEL t s)  t∈Itype
  s∈Stringで示されるロケーション。

##### Reg 式

ここではReg式に対する意味を定義する。マシンの自然なワード長より小さな単位での演算等で、オペランドに指定されたレジスタの一部にアクセスする場合がある。そのような部分的なレジスタを、元のレジスタの部分レジスタという。

以下の定義が使われるのはReg式がSet式の第一引数以外で、そのレジスタが格納している値を取り出すという場合にかぎられるようにSet式が定義されている。

(REG t s)
  s∈Stringで示されるレジスタの値。
(SUBREG t x n)

  xで指定されるレジスタのn番目の部分レジスタの値。

  例えば、(SUBREG I8 (REG I32 "x") 2)は、xレジスタのbit16〜bit23を、(SUBREG I10 (REG I32 "x") 1)は、xレジスタのbit10〜bit19を意味する。

##### Pure 式

(NEG t x)  t = tx（型は変わらない）
  符号反転。
(ADD t x y)  t = tx = ty
  加算。
(SUB t x y)  t = tx = ty
  減算。
(MUL t x y)  t = tx = ty
  乗算。
(DIVS t x y)  t = tx = ty
  符号つき除算。
(DIVU t x y)  t∈Itype∧t = tx = ty
  符号なし除算。
(MODS t x y)  t∈Itype∧t = tx = ty
  符号つき剰余。
(MODU t x y)  t∈Itype∧t = tx = ty
  符号なし剰余。
(CONVSX t x)  t,tx∈Itype
  符号拡張。
(CONVZX t x)  t,tx∈Itype
  ゼロ拡張。
(CONVIT t x)  t,tx∈Itype
  精度の低い整数へ。
(CONVFX t x)  t,tx∈Ftype
  精度の高い浮動小数へ。
(CONVFT t x)  t,tx∈Ftype
  精度の低い浮動小数へ。
(CONVFI t x)  t∈Itype∧tx∈Ftype
  浮動小数から整数へ。
(CONVSF t x)  t∈Ftype∧tx∈Itype
  符号つき整数から浮動小数へ。
(CONVUF t x)  t∈Ftype∧tx∈Itype
  符号なし整数から浮動小数へ。
(BAND t x y)  t∈Itype∧t = tx = ty
  論理積。
(BOR t x y)  t∈Itype∧t = tx = ty
  論理和。
(BXOR t x y)  t∈Itype∧t = tx = ty
  排他的論理和。
(BNOT t x)  t∈Itype∧t = tx
  論理否定。
(LSHS t x y)  t,ty∈Itype∧t = tx

  符号つき左シフト。

  ４つあるシフト命令において、左シフト、右シフトの区別はシフトカウントが正の場合の向きによる。

(LSHU t x y)  t,ty∈Itype∧t = tx
  符号なし左シフト。
(RSHS t x y)  t,ty∈Itype∧t = tx
  符号つき右シフト。
(RSHU t x y)  t,ty∈Itype∧t = tx
  符号なし右シフト。
(TSTEQ t x y)  t∈Itype∧tx = ty
  比較(x = y)。
(TSTNE t x y)  t∈Itype∧tx = ty
  比較(x≠y)。
(TSTLTS t x y)  t∈Itype∧tx = ty
  符号つき比較(x < y)。
(TSTLES t x y)  t∈Itype∧tx = ty
  符号つき比較(x≦y)。
(TSTGTS t x y)  t∈Itype∧tx = ty
  符号つき比較(x > y)。
(TSTGES t x y)  t∈Itype∧tx = ty
  符号つき比較(x≧y)。
(TSTLTU t x y)  t,tx∈Itype∧tx = ty
  符号なし比較(x < y)。
(TSTLEU t x y)  t,tx∈Itype∧tx = ty
  符号なし比較(x≦y)。
(TSTGTU t x y)  t,tx∈Itype∧tx = ty
  符号なし比較(x > y)。
(TSTGEU t x y)  t,tx∈Itype∧tx = ty
  符号なし比較(x≧y)。
(ASMCONST t x)  t = tx∧isasmconst x
  意味はxと同じである。ここにisasmconstはリンカが解決出来る定数かどうかを判定するUnspecified関数である。(現在はサポートされていない)
(PURE t x)  x∈IntConstExp
  副作用のない任意の演算。拡張用。(現在はサポートされていない)

##### Mem 式

(MEM t x)  tx∈Itype
  データメモリのアドレスxにある型tのオブジェクトが格納している値。m∈MemModifierが存在し、m=Vの時にかぎりMem式はvolatileオブジェクトを表し、読み込みがトレースに記録され、結果は予測不能値となる。

##### Set 式

ここではSet式に対する意味を定義する。

(SET t (MEM t' x [& m]) y)  t=t'=ty
  データメモリのアドレスxにある型tのオブジェクトへyの値を代入する。m∈MemModifierが存在し、m=Vの時にかぎりMem式はvolatileオブジェクトを表し、書き込みがトレースに記録される。
(SET t (REG t' s) x)  t=t'=tx
  Reg式が表すレジスタにxの値を代入する。
(SET t (SUBREG t' (REG tx s) n) x)  t=t'=tx
  SubReg式が表す部分レジスタにxの値を代入する。m∈SubregModifierが存在し、m=Nの時にかぎり(REG tx s)中の指定部分以外に予測不能値が入る。(現在、SubregModifierはサポートされていない)

##### Jump 式

(JUMP l)
  ラベル式lで示されるロケーションへジャンプする。
(JUMPC x l1 l2)  x.code∈TstOps
  Tst式xの値が1ならl1へ、0ならl2へジャンプする。
(JUMPN x ((c1 l1)…(cn ln)) l0)  tx∈Itype∧i≠j⇒ci≠cj
  整数式xの値がci∈Zに等しければliへジャンプ、そうでなければl0へジャンプする。

##### DefLabel 式

(DEFLABEL s)
  ラベルを定義する。

##### Call 式

ここではCall式の意味を定義する。

(CALL x1 (x2…xn) (y1…ym))
  x1の値で示されるプログラムメモリにL関数があると仮定し、多値関数と解釈して、引数x2…xnを与え、結果の多値をy1…ymに代入する。

##### Interface 式

ここではInterface式の意味を定義する。

(PROLOGUE (wf wr) x1…xn)

  wfはフレームのサイズで、wrはレジスタフレームのサイズ（現在は使われていない）。 xiは仮引数。

(EPILOGUE (wf wr) x1…xn)

  wfはフレームのサイズで、wrはレジスタフレームのサイズ（現在は使われていない）。 xiは返り値。

##### Special 式

(PARALLEL x1…xn)
  x1,…,xnの副作用を同時に行なう。xiはSET, USE, CLOBBERのいずれかで、PHIは含まない。
(USE r1…rn)
  レジスタr1からrnが使用されることを表す。
(CLOBBER x1…xn)
  構文からx1,…,xnはSet式の第一引数に許されるものであり、そこに予測不能値が入ることを表す。
(PHI x (x1 l1)…(xn ln))

  Φ関数( x = Φ(x1,…, xn) )。

  ここでxi(1≦i≦n)の値は、対応するラベル式li(1≦i≦n)が示す先行基本ブロック(predecessor)の一つから伝えられ、新しい変数x(REG式)にマージされる。

##### IF式

(IF t cond then else)  t = tthen = telse
  Tst式condを評価し、結果が真ならばthen、偽ならばelseの値を返す式。その式の型はtである。

##### LINE式

(LINE N)
  この次のL式がソース中の第N行目に対応していることを示す。

#### 変更された点

LIR仕様書（pdf） (以下「仕様書」と略す)からは以下の点が変更された。

Aggregate Type
  構造体や配列を表現するAggregate Typeは、「仕様書」ではただの10進数であったが、プリフィックスAに10進数が続く形に変更された。
ALIST→SYMTAB
  記号表を示すキーワードは「仕様書」ではALISTだったが、本定義ではSYMTABに変更された。
<RegSymbol>にalignフィールド
  <RegSymbol>の形式にalignフィールドが追加され、<FrameSymbol>と同様の形式になった。
USE, CLOBBERのオペランド数
  「仕様書」ではUSE,CLOBBERは一つのオペランドしか許されていないが、本定義では二つ以上のオペランドを許すように変更された。
LINE
  ソース中の行番号の情報を伝えるLINE式が追加された。

### 4.6. LIRの読み方

LIRが表現するものの意味を、図4-2の２つのCプログラム、`main.c`と `sub.c`、の例で説明する。 このプログラムの関数`prodv`は、関数`fold1`を使って、 配列`v`のすべての要素の積の値を返す。

    main.c :   extern float fold1(float f(float,float), float v[], int n);
               static float v[] = {1, 2.5, 3};
               static int n = sizeof v / sizeof v[0];
               static float fmul(float x, float y){float r=x*y; return r;};
               float prodv(){return fold1(fmul,v,n);};

    sub.c :    float fold1(float f(float,float), float v[], int n)
               {
                 int i; float r;
                 for (r=v[0], i=1; i<n; i++) r = f(r,v[i]);
                 return r;
               }

図4-2 Cプログラム例
最初のCプログラム`main.c`は図4-3に示すLIRコード（L-moduleと呼ばれる） に変換される。 この情報は、以下のオプションを指定したときに出力される。

    -coins:trace=LIR

LIRでは`int`、`pointer`、 `float`はすべて３２ビット長であると仮定し、それらの必要なアラインメントは ４バイト境界であると仮定している。 マシン命令は`text`セグメントに置かれ、データは`data`セグメントに置かれる。

     1 (MODULE "main.c"
     2   (SYMTAB
     3     ;; name  class  L-type align segment linkage
     4     ("prodv" STATIC UNKNOWN  4   ".text" XDEF)
     5     ("fmul"  STATIC UNKNOWN  4   ".text" LDEF)
     6     ("n"     STATIC I32      4   ".data" LDEF)
     7     ("v"     STATIC A96      4   ".data" LDEF)
     8     ("fold1" STATIC UNKNOWN  4   ".text" XREF))
     9   ;; definition of the function fmul
    10   (FUNCTION "fmul"
    11     (SYMTAB
    12       ("x.1" FRAME F32 4 0)
    13       ("y.2" FRAME F32 4 0)
    14       ("r.3" FRAME F32 4 0)
    15       ("returnvalue.4" FRAME F32 4 0))  ; generated by the translator
    16     ;; L-sequence
    17     (PROLOGUE (0 0) (MEM F32 (FRAME I32 "x.1")) (MEM F32 (FRAME I32 "y.2")))
    18    (DEFLABEL "_lab1")
    19     (SET F32 (MEM F32 (FRAME I32 "r.3"))     ; r = x*y
    20              (MUL F32 (MEM F32 (FRAME I32 "x.1"))
    21                       (MEM F32 (FRAME I32 "y.2"))))
    22     (SET F32 (MEM F32 (FRAME I32 "returnvalue.4")) (MEM F32 (FRAME I32 "r.3")))
    23     (JUMP (LABEL I32 "_epilogue"))
    24    (DEFLABEL "_epilogue")
    25     (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.4"))))
    26   ;; definition of the function prodv
    27   (FUNCTION "prodv"
    28     (SYMTAB
    29       ("returnvalue.5" FRAME F32 4 0)     ; generated by the translator
    30       ("functionvalue.6" FRAME F32 4 0))  ; generated by the translator
    31     (PROLOGUE (0 0))
    32    (DEFLABEL "_lab3")
    33     (CALL (STATIC I32 "fold1")     ; functionvalue.6=fold1(fmul,v,n)
    34           ((STATIC I32 "fmul") (STATIC I32 "v") (MEM I32 (STATIC I32 "n")))
    35           ((MEM F32 (FRAME I32 "functionvalue.6"))))
    36     (SET F32 (MEM F32 (FRAME I32 "returnvalue.5")) (MEM F32 (FRAME I32 "functionvalue.6")))
    37     (JUMP (LABEL I32 "_epilogue"))
    38    (DEFLABEL "_epilogue")
    39     (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.5"))))
    40   ;; definition of the data v and n
    41   (DATA "v" (F32 (FLOATCONST F32 1.0) (FLOATCONST F32 2.5) (FLOATCONST F32 3.0)))
    42   (DATA "n" (I32 3)))

図4-3 `main.c`のLIRコード
セミコロンはコメントの始まりを示す。その行の終わりまでがコメントである。 左端の数字は説明のために付けた行番号である。

Lモジュール（L-module）はモジュール名、（グローバル）シンボルテーブル、L関数の定義、Lデータ からなる。 L関数は、その名前、（ローカル）シンボルテーブル、Lシーケンスからなる。 Lシーケンスは、L式のリストであり、 `PROLOGUE`式で始まり、 `EPILOGUE`式で終わる。 Lデータは、その名前とその内容のリストからなる（41，42行）。

シンボルテーブルは、キーワード`SYMTAB`で始まり、 いくつかのエントリからなる。各エントリの最初の要素は名前である。 2番目の要素はクラスと呼ばれ、それによってそれ以後の要素のシンタックスや意味が決まる。 シンボルテーブルで宣言された名前は、それ以後の同じ静的スコープの中のL式で参照される。

クラスが`STATIC`である名前は静的に割り付けられるオブジェクトを表す。 クラスが`FRAME`である名前はスタックフレームに割り付けられるオブジェクトを表す。 たとえば、Lモジュール`main`の6行目の名前`n`は、 静的に割り付けられるオブジェクト で、L型は`I32`(32ビット整数)と宣言されている。 さらに、この宣言はアラインメント、セグメント、リンケージの情報を持っている。この例では、アラインメントは4バイト境界、 セグメントはデータセグメント、リンケージは`LDEF`となっている。 リンケージには`LDEF`、`XDEF`、`XREF`の3種類があり、それぞれ、ローカルな定義、グローバルな定義、外部参照を表す。

12行目は`x`の宣言であるが、他のローカル変数と区別出来るように、番号を付けたユニークな名前`x.1`としている。`x.1`はフレーム変数でありL型は`F32`（32ビットの浮動小数点数） である。その次の`４`はアラインメントである。最後の`０`のあるところは フレームポインタからのオフセットを入れる場所であるが、この段階（最初にLIRを生成したとき）ではまだ その計算はしてないので、すべて`０`が入っている。バックエンドの処理が進んだ段階で、オフセットが計算される。 LIRでは、フレームポインタの存在は仮定しているが、それは陽には現れない。

7行目では、変数`v`のL型は`A96`となっている。これは96ビットのオブジェクトを表す。 L型は以上に出てきた、nビット整数の`I` n、 nビット浮動小数点数の`F` n、nビットの`A` n の3種類ですべてである。 `UNKNOWN`はコンパイラにとってサイズの分からないものを示すのに使われる。 `UNKNOWN`はL型ではない。

10行目からは、関数定義の例を示している。２つのL式、`PROLOGUE`式と `EPILOGUE`式、はL関数のインターフェースを明示している。これらはインターフェース式と呼ばれる。 17行目の`PROLOGUE`式の2番目の要素`(0 0)`はフレームのサイズとレジスタフレームのサイズ を示すものとして設計されたが、現在は使われておらず、常に`(0 0)`となっている。25行目の `EPILOGUE`式の2番目の要素も同様である。 `PROLOGUE`式の残りの要素はL関数の仮引数を示している。 `EPILOGUE`式の残りの要素はL関数の返す値を表す式のリストである。

19行目はL式の例である。対応するCのコード`"r=x*y"`と違って、メモリーアクセスを `(MEM type address)`という形で 陽に表現している。 `(FRAME I32 "x.1")`というフレーム式は、12行目で宣言された変数`x.1`のアドレスを表している。`I32`はアドレス型の型である。

33行目は関数呼び出しの例である。そのシンタックスは

      (CALL addr (args ... ) (results ...))

という形である。ここで、 addrは呼ばれる関数のアドレスであり、 argsは関数に渡される実引数のL式であり、 resultsは関数の戻り値が代入される変数である。戻り値が複数個ある場合も表現出来るようになっている。 　CALL式を他のL式の中に直接書くことは出来ないので、一時的な変数として`functionvalue.6`が トランスレータによって導入されている。

３４行目は、グローバル変数にアクセスする例である。 L式`(MEM I32 (STATIC I32 "n"))`は６行目で宣言された変数`n` のアドレスを表している。

この例ではレジスタが現れていないが、LIRではレジスタは `(REG type name)`の形で表される。そして、 name はシンボルテーブルの中で `(name `REG` type offset)` の形で宣言される。ここで、typeはそのレジスタの型である。 レジスタのoffsetの値は実際には使われておらず、常に0である。 バーチャルレジスタも、リアルレジスタも同じ形である。

以上のように、我々の関数呼び出しの形は、GCCのRTLでのそれより 高水準である。

関数呼び出しを実際のマシンの呼び出し規約（calling convention) にしたがって実現するのは呼び出し規約展開（calling convention expansion） と呼ばれるが、 GCCでは、コンパイル過程の早い時期に呼び出し規約展開をやってしまい、 実レジスタを明示してしまう。そのようなGCCの利点は、マシンに依存した各種の 最適化が可能になることであるが、欠点は、最適化が非常に複雑になることである。

`sub.c`は図4-4に示すLIRコード（L-module） に変換される。この例には制御構造が入っている。

     1 (MODULE "sub.c"
     2   (SYMTAB
     3     ("fold1" STATIC UNKNOWN 4 ".text" XDEF))
     4   (FUNCTION "fold1"
     5     (SYMTAB
     6       ("f.1" FRAME I32 4 0)
     7       ("v.2" FRAME I32 4 0)
     8       ("n.3" FRAME I32 4 0)
     9       ("i.4" FRAME I32 4 0)
    10       ("r.5" FRAME F32 4 0)
    11       ("returnvalue.6" FRAME F32 4 0))
    12     (PROLOGUE (0 0) (MEM I32 (FRAME I32 "f.1"))
    13                     (MEM I32 (FRAME I32 "v.2"))
    14                     (MEM I32 (FRAME I32 "n.3")))
    15    (DEFLABEL "_lab1")
    16     (SET F32 (MEM F32 (FRAME I32 "r.5"))      ; r = v[0]
    17              (MEM F32 (ADD I32 (MEM I32 (FRAME I32 "v.2"))
    18                                (MUL I32 (INTCONST I32 4) (INTCONST I32 0)))))
    19     (SET I32 (MEM I32 (FRAME I32 "i.4"))      ; i = 1
    20              (INTCONST I32 1))
    21    (DEFLABEL "_lab5")
    22    (JUMPC (TSTLTS I32 (MEM I32 (FRAME I32 "i.4"))   ; if (i<n) goto _lab6; else goto _lab4
    23                       (MEM I32 (FRAME I32 "n.3"))) (LABEL I32 "_lab6") (LABEL I32 "_lab4"))
    24   (DEFLABEL "_lab6")
    25    (CALL (MEM I32 (FRAME I32 "f.1"))          ; r = f(r,v[i])
    26          ((MEM F32 (FRAME I32 "r.5"))
    27           (MEM F32 (ADD I32 (MEM I32 (FRAME I32 "v.2"))
    28                             (MUL I32 (INTCONST I32 4)
    29                                      (MEM I32 (FRAME I32 "i.4"))))))
    30          ((MEM F32 (FRAME I32 "r.5"))))
    31   (DEFLABEL "_lab3")
    32    (SET I32 (MEM I32 (FRAME I32 "i.4"))       ; i++
    33             (ADD I32 (MEM I32 (FRAME I32 "i.4"))
    34                      (INTCONST I32 1)))
    35    (JUMP (LABEL I32 "_lab5"))
    36   (DEFLABEL "_lab4")
    37    (SET F32 (MEM F32 (FRAME I32 "returnvalue.6")) (MEM F32 (FRAME I32 "r.5")))
    38    (JUMP (LABEL I32 "_epilogue"))
    39   (DEFLABEL "_epilogue")
    40    (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.6")))))

図4-4 `sub.c`のLIRコード
`if`や`whileなどの`構造的な(structured)制御構造はない。 `(DEFLABEL label)`式はラベルlabelを定義する。 ラベルはジャンプ式で参照される。３５行目では無条件ジャンプ式で参照され、２２行目では条件ジャンプ式で参照されている。 ２５行目は間接呼び出しの例である。`CALL`式のアドレス式はL関数のアドレスにならなければならない。 また、ジャンプ式のターゲットはそのジャンプのある関数の中になければならない。

もう一つの例として、 3.2 HIRによるプログラムの表現の図3-2にあげたHIRに対応するLIRを次の図4-5に示す。 このような出力は、

    -coins:trace=LIR

というオプションを指定することによって得られる。その場合、 最初に生成されたLIRではなく、その制御フローグラフを作った後のものが出力される。

     1 Module "fact0.c":
     2 Global Symbol table:
     3   ("memcpy" STATIC UNKNOWN 4 "text" XREF)
     4   ("__dtoll" STATIC UNKNOWN 4 "text" XREF)
     5   ("__ftoll" STATIC UNKNOWN 4 "text" XREF)
     6   (".stackRequired" STATIC UNKNOWN 4 "abs" XREF)
     7   ("fact" STATIC UNKNOWN 4 ".text" XDEF)
     8 Function "fact":
     9  Local Symbol table:
    10   ("p.1" FRAME I32 4 0)
    11   ("returnvalue.2" FRAME I32 4 0)
    12   ("functionvalue.3" FRAME I32 4 0)
    13 Control Flow Graph:
    14   #1 Basic Block (.L1): DFN=(1,1), <-() ->(#2)
    15     (PROLOGUE (0 0) (MEM I32 (FRAME I32 "p.1")))
    16     (JUMP (LABEL I32 ".L3"))
    17   #2 Basic Block (.L3): DFN=(2,2), parent=#1, <-(#1) ->(#3,#5)
    18     (JUMPC (TSTLES I32 (MEM I32 (FRAME I32 "p.1")) (INTCONST I32 1)) (LABEL I32 ".L4") (LABEL I32 ".L5"))
    19   #3 Basic Block (.L4): DFN=(3,4), parent=#2, <-(#2) ->(#6)
    20     (SET I32 (MEM I32 (FRAME I32 "returnvalue.2")) (INTCONST I32 1))
    21     (JUMP (LABEL I32 ".L6"))
    22   #4 Basic Block (.L2): DFN=(0,0), <-() ->(#6)
    23     (JUMP (LABEL I32 ".L6"))
    24   #5 Basic Block (.L5): DFN=(5,3), parent=#2, <-(#2) ->(#6)
    25     (CALL (STATIC I32 "fact") ((SUB I32 (MEM I32 (FRAME I32 "p.1")) (INTCONST I32 1)))
    26       ((MEM I32 (FRAME I32 "functionvalue.3))))
    27     (SET I32 (MEM I32 (FRAME I32 "returnvalue.2")) (ML I32 (MEM I32 (FRAME I32 "p.1"))
    28       (MEM I32 (FRAME I32 "functionvalue.3"))))
    29     (JUMP (LABEL I32 ".L6"))
    30   #6 Basic Block (.L6): DFN=(4,5), parent=#3, <-(#3,#4,#5) ->()
    31     (EPILOGUE (0 0) (MEM I32 (FRAME I32 "returnvalue.2")))
    32 End Function
    33 End Module

図4-５　制御フロー作成後のLIRの例

３行目から６行目までは、ソースプログラムにはなかった名前が導入されている。 "memcpy"、"__dtoll"、"__ftoll"は、生成されたコードから引用されるかもしれないライブラリ関数 やサブルーチンの名前である。実際に生成されたコードでは使われていない場合 もある。
最後の".stackRequired"はややトリッキーで、sparc.tmdでのみ使用している。 組み込み関数allocaの展開中にある定数を引用しているが、その値が最 後にフレームサイズが確定するまで決まらないため、当面その定数をこのシン ボルのアドレスとして表現しておき、後に整定数に置きかえている。 そのため、このシンボル自体は最終的なコードでは不要となる。

13行目から31行目までは、制御フローグラフの中にLIRが入っている形である。 たとえば、17行目の

     #2 Basic Block (.L3): DFN=(2,2), parent=#1, <-(#1) ->(#3,#5)

は基本ブロック番号が2であり、その先頭に`.L3`というラベルがついていることを示す。
`DFN=(x,y)`の`DFN`はDepth First Numberの意味であり、x はpreorderの番号、yはreverse postorderの番号である。`parent=#2`は depth first spanning treeでのparentブロックの番号が２であることを示す。`<-(#1) ->(#3,#5)`は先行ブロック が`#1`であり、後続ブロックが`#3`と`#5`であることを示す。

22,23行目のブロック４は到達しない（unreachableな）ブロックである。これは、if文のthen部に機械的に挿入されたものであり、 then部の最後がreturn文であったためにunreachableになっている。このようなブロックは後のフェーズの ジャンプ最適化で削除される。

### 4.7. LIRの詳細仕様

LIRの詳細仕様についてはLIR仕様書（pdf） を参照されたい。

その他にLIRの文書として LIR解説(html)、 LIR内部構造(html)、 研究会資料（pdf）、などを参照されたい。