2004/5/22, 6/9, 8/15 　Ｉ．　共通中間表現仕様の概要 　　　　　　　　　　　　　　　　　　　　(##24) 2004/5-6改訂 　　　　　　　　　　　　　　　　　　　　(##21) 2003/6改訂 　　　　　　　　　　　　　　　　　　　　(##14) 2002/6改訂 　　　　　　　　　　　　　　　　　　　　(##11) 2002/1改訂 １・　仕様書の構成 (##11) 　「並列化コンパイラ向け共通インフラストラクチャの研究」（略称 COINS(Compiler Infrastructure)プロジェクト）で開発するコンパイラの共通 中間表現の仕様は、次の書類ないしインタフェース仕様によって記述されてい る。 　　仕様概要 　　　共通中間表現仕様の概要（本仕様書IrOutline.txt） 　　　高水準中間表現の概要 (HirOutline.txt) 　　　高水準中間表現の型と意味 (HirType.txt) 　　　低水準中間表現の概要 　　　COINSプロジェクトLIR仕様書 　　　記号表の概要 　　　フロー情報の概要 　　インタフェース仕様（Javaのinterfaceとして記述。 　　　　　日本語で改めて書く予定はない。） 　　　HIR.java　　高水準中間表現のインタフェース仕様 　　　Sym.java　　記号表のインタフェース仕様 　　　Type.java　　型のインタフェース仕様 　　　Flow.java　　フロー情報のインタフェース仕様 　　　BBlock.java フロー解析に使う基本ブロックのインタフェース仕様 　　　MachineParam.java　　対象機種依存情報のクラス 　　　SourceLanguage.java　入力言語依存情報のクラス 参照順序としては、次のように読み進められたい。 （１）本仕様書 （２）それぞれの項目の仕様概要 （３）上記のインタフェース仕様を記載したJava interface （４）上記のJava interfaceの下位クラスとしてのJava interface 仕様概要にはどのような考えによって設計したかは書いてあるが、個々のメソ ッドの仕様は書いていない。それらについてはインタフェース仕様を参照され たい。 　本コンパイラの設計にあたっては、利用者はインタフェース仕様を見れば理 解でき、その実現内容までは見なくてよいようにすることを意図した。インタ フェース仕様は、まず上記の上位クラスのメソッド仕様を見て、そこに記載さ れているもので表現できないことについてはその下位クラスのインタフェース 仕様を見るようにする。下位クラスのインタフェース仕様を見ることによって 同じ処理ができないわけではないが、いろいろの約束事をよく心得た上でない と、誤った使い方をする恐れがあるので、必ず上位クラスのインタフェースを 見てそこに書かれているメソッドによってできることはそれらによって実現さ れたい。インタフェース仕様に書かれた備え付けメソッドを使わないでHIRや LIR、記号表のインスタンスを生成したり変更したりすることは、他のメソッ ドがうまく機能しなくなることがあるので、行うべきでない(##21)。 　仕様概要においては、入力言語(source language)や対象機種(target machine)に依存しない記述を中心とするが、その途中で特定言語、特定機種の 場合について説明することもある。このような特定言語、特定機種についての 説明は、その前後を[[ ]]で囲んで、他と区別する。 　中間表現に限るわけではなく、コンパイラ全体の制御に関係するクラスとし ては、次のものがあり、中間表現の仕様で参照されることがある。 　　　Driver コンパイラのパスの制御 　　　IoRoot 入出力関連情報へのリンク 　　　SymRoot 記号表関連へのリンク 　　　HirRoot HIR情報へのリンク 　　　LirRoot LIR情報へのリンク 　　　FlowRoot フロー情報へのリンク 　　　Message メッセージ出力制御 　　　Debug デバッグ出力制御 ２．中間表現の設計方針 ２．１　全体的方針 （１）処理を共通化可能にする中間表現 　コンパイラにおける処理の中核部を、多くの言語、多くの機種に対して共通 化できれば、その共通化されたものを基盤として、いろいろのコンパイラを容 易に作ることができるようになる。それを可能にするには、コンパイラの構成 要素間のインタフェースとなる中間表現(IR, intermediate representation) を共通化する必要がある。ここでは、どのようにすればそれを共通化できるか を考察し、共通中間表現の具体化方針を提示する。ただし、共通化といっても、 完全な共通化を意味するのではなく、「コンパイラの処理モジュールを言語間、 機種間でできる限り共通部分を多く作れるようにし、依存部分は小さい手続き やクラスに閉じこめることができるようにする」という意味での共通化である。 　ここで言う共通中間表現は、中間表現の構文(syntax)ないし意味 (semantics)をいくつかの入力言語、いくつかの対象機種の間で共通な形で定 めてあるということであり、それで表現された中間表現インスタンスが言語間、 機種間で完全に共通というわけではない。共通な構文の枠組みの中で、特定の 入力言語、特定の対象機種に合わせた表現が含まれることはある。具体的コン パイラを作るときは、入力言語と対象機種を特定のものに定めて作ることが多 いので、このようにしても、構文が共通なので、コンパイラの処理の多くの部 分を共通化することができる。　(##11) 　なお、本コンパイラインフラストラクチャの記述言語はJavaとし、依存部 分を小さく明示的にまとめるのに、クラス機能など、Java言語の特性も利用 する。コンパイルに使う計算機（ホスト計算機）は、Javaが利用でき、100メ ガバイト以上の主記憶とファイルシステムを有する計算機とする。 （２）中間表現に対する要求 　コンパイラにおける中間表現に対しては、一般に、次のようなことが要請さ れる。 　　・プログラムの構造や意味内容を曖昧さなく表現できる。 　　・プログラムの解析や変換に適した表現形態である。 　　・最適化、並列化、レジスタ割付などに必要な情報をうまく表現できる。 　　・拡張性に富む。 　　・処理時間やメモリ使用量が少ない。 本プロジェクトでは、各種の言語や機種に対する並列化コンパイラの共通の基 盤を作ることを目指している。その利用者は、応用プログラム開発者であるこ ともあるが、主としてコンパイラ開発者であることを想定している。したがっ て、拡張性に富むことが非常に重要であり、次のことが求められる。 　　・他言語、他機種への展開が容易である。 　　・長年月にわたる機能の追加、改訂に容易に対処できる。 本仕様は、このような要求に応えられるように設計した。 ２．２　中間表現のレベル設定 　プログラムの解析や変換では、手続き(procedure)単位やループ単位で並列 性を認識するとか、ループ変換やインライン展開など、大きいかたまりを単位 として扱う場合がある。また、並列化などの変換をした結果をまたソースプロ グラムの形で出力する場合もある。このような場合には、入力プログラムの構 造を反映できる中間表現が求められる。一方、コンパイラでは、レジスタ割付 や命令スケジューリングなど、細かいレベルでの処理も要求され、そのような 場合は機械命令に近い中間表現が求められる。本コンパイラの利用者としては、 新しい言語に対するコンパイラの開発者や、既存言語に対して新しい対象機種 用のコンパイラを作る開発者など、さまざまな場合が考えられ、その利用形態 は、上記のどちらか一方の形態であることも多いと思われる。そこで、中間表 現としては、入力プログラムの構造を反映できる高水準中間表現と、計算機に よる処理の特性を反映できる低水準中間表現の２つを設定するのがよい。各中 間表現の具体的利用形態としては、次のようなものが想定される。 高水準中間表現向き処理 　　逐次実行型プログラムから並列実行型のプログラムへの 　　　入力言語と同レベルでの変換（SMP向き階層的並列化、他） 　　入力プログラムを実行効率が良くなるように変換する 　　　入力言語と同レベルでの最適化 　　ループ解析（配列要素の依存関係、並列実行性抽出、等） 　　インライン展開 　　ループ変換（ループ展開、タイリング、他） 　　手続きやループ等の大きい単位での並列化変換 　　各種プログラミングツールの開発 　　　（ソフトウェア工学的な解析、変換、他） 　　別名解析(alias analysis) 　　他 低水準中間表現向き処理 　　レジスタ割付 　　詳細レベルの（データのアクセスパスを考慮した）最適化 　　命令スケジューリング 　　　（スーパースカラ向き変換、トレーススケジューリング、他） 　　命令レベル並列化（マルチメディア向き並列化、VLIW並列化、他） 　　計算機資源（レジスタ、演算器等）に合わせた最適化、並列化 　　ピープホール最適化 　２段階にすると、コンパイル時間がかかるとか、フロー解析が２度必要にな るなどの問題もあるが、最適化や並列化の過程では、いずれにしても中間表現 を複数回走査しなければならず、プログラム構造を改変すればフロー解析もや りなおさなければならないので、処理時間の面からの問題は比較的小さい。２ 段階あるとフロー解析や走査などの処理プログラムが２重に必要になるとの指 摘もあるであろうが、それらの処理の多くは共通化することができる。プログ ラムの解析や変換は、大きいかたまりでとらえる場合と、個々の命令のような 小さい単位で行なう場合とで、異なる方式を考えなければならないことも多い。 ２段階あることによるプログラミングの負担増よりも、２段階にすることによ る処理のしやすさの効用の方が大きい。 ２．３　記号表の役割　(##11) 　プログラムには、変数や副プログラムなどの記号が現れる。これらは文字列 のままでは扱いにくいので、記号表(symbol table)に登録し、中間表現では記 号表の記載項（エントリ）として扱う。記号に関する種々の属性は記号表の記 載項に付与する形で記録する。これらの属性には、宣言文やプログラム構造な どによって決まるものや、構文解析、意味解析のときに設定されるものが多い。 高水準中間表現や低水準中間表現は処理操作を中心として表現するものであり、 宣言文の抽象構文木(abstract syntax tree)は表現しない。そこで記号の情報 は記号表に記載する。 　記号表には、変数や副プログラムに限らず、定数や型名、コンパイラ内部で 生成するレジスタ、一時変数など、コンパイル過程で参照される記号をすべて 記載する。定数は記号表に記載する必要はないとの意見もあるであろうが、定 数が必ずしも１語で表わされるとは限らず、コンパイル環境と対象機種によっ て定数の表現精度や表現範囲が異なる、あるいは定数にもレジスタ割付情報を 付加するなどの使い方も考えられるので、定数も記号表に記載する。記号には、 入力言語に依存する情報や対象機種に依存する情報も含まれるが、それらは必 要になったときに参照すればよいのであって、コンパイルの過程では、入力言 語や対象機種に固有の情報まで参照しなくてもできる処理がたくさんある。記 号表を使うことによって、コンパイラの処理の多くを共通化できる。 　　プログラム　＝　操作の中間表現　　＋　　　記号表 　　　　　　　　　　（実行文の内容）　　（宣言文等の情報） ３．高水準中間表現 ３．１　要素的言語に対する抽象構文木 　プログラミング言語の文法は、手続き型言語に限っても、言語ごとに大きく 異なるが、現在広く使われているものを見ると、概念的に共通する部分が多い。 これらの共通部分を抽出して、それに幾つかの要素的言語機能を加えると、一 つの小さい要素的言語を構成できる。例えば、多くの言語には、基本的データ 型としては整数、浮動小数点数、文字、ポインタなどがあり、それらに基づい て、配列、構造体、共用体などの複合されたデータ構造が構成される。それら に対する操作として、算術演算、論理演算、比較演算などの演算があり、代入 文、選択文、反復文、goto文などの文がある。処理のまとめ方としては、副 プログラムやクラスなどの概念がある。このような概念をある詳しさのレベル でまとめると、１つの言語を構成することができる。そこでは、ある言語機能 がより基本的な言語機能で表現できるとすれば、分解した形で表現する。ただ し、現代の計算機が持っている基本機能以下にまで分解することはしない。こ のような要素的言語を人がプログラム記述に使う言語として定めることは、も との言語の間の違いが大きすぎるのでむずかしいが、中間表現としては設定可 能である。高水準中間表現は、このような考え方に基づいて設定した。 　中間表現の一つの形態として、抽象構文木(abstract syntax tree)がある。 これは構文木(syntax tree)のうち、演算に本質的に必要な部分だけ取り出し、 構文を明確にするための区切り記号等を省略した木構造の表現である。これに はまだ入力言語の構文が反映されているが、上に述べたように、現行の手続き 型言語に共通的な概念を抽出して設定した要素的言語を想定し、それに対する 抽象構文木を考えるならば、特定の言語に依存しない形で、共通中間表現を定 めることができる。具象表現は類似していても、言語によって意味内容の異な るものが種々ある。共通中間表現では、これらについて、その具象表現にとら われず、必要とあればより基本的な言語機能に分解して表現する。副プログラ ム構造やクラス、スコープ、呼び出し形式、演算順序などの違いは、このよう な方法によって言語ごとの意味解析部で吸収でき、入力言語を共通の抽象的表 現に変換できる。ここではそのような抽象構文木に対応する表現を HIR (High level Intermediate Representation) と呼ぶ。HIRには文字列としての表現 （テキスト表記）もあるが、木構造(tree)としての表現もあり、両者は等価で ある。木構造として表現する場合、それは子供を持つ節（nonleaf）と子供を 持たない葉（leaf）から構成される。節も葉もノードと総称する。節は演算や 構造などを指定する演算子を持ち、葉は変数名や副プログラム名、定数などの 記号を表す。 　入力言語では明示的に表されていない隠れた操作も、中間表現では明示的に 表す。例えば、初期値の暗黙設定や、オブジェクトの生成、代入や演算、引数 渡しに伴う型変換、初期化の処理などに対しては、それらを表現する式や文を 挿入する。 　HIRの抽象構文木の構造はBNFで記述されており、その意味は「高水準中間 表現の型と意味」の仕様書に記述されている。HIRの葉などからは記号表を参 照する。HIRと記号表を合わせたものは１つの言語とみなすことができる。記 号表に対しても、あとで述べるように、テキスト表記が定められている。１つ のプログラムのHIRと記号表を合わせてテキスト表記したものは、高水準中間 表現をテキスト表記したプログラムと見なすことができる。 ３．２　高水準中間表現における型　(##14) 　プログラムは、計算機処理の対象に対して何がしかの処理を指定するものと みなすことができる。処理対象は、同じ扱いのできるもの（同じ処理を適用で きるもの、同じ表現規則に従うもの）という基準でグループ化できる。型は、 そのようにして構成したグループとみなすことができる。整数という表現形式 と整数演算という処理を中心として同じ扱いができるグループを整数型といい、 浮動小数点という表現形式と浮動小数点演算という処理を中心として同じ扱い ができるグループを浮動小数点型というなどということを進めていって、各々 のプログラミング言語における型システムが定められる。 　高水準中間表現HIRでは、多くのプログラミング言語に共通する型を抽出し、 それをHIRの型とする。その型については「高水準中間表現における型と意 味」で詳しく説明することにし、ここでは設計の方針を述べる。 　基本型としては、整数、浮動小数点、文字、bool, void等を設ける。それ らのうちにはさらに細分化されるものもある。基本型に基づいて構成される型 として、ポインタ、配列(array)、構造体(structure)、共用体(union)、列挙 (enumeration)等を設ける。副プログラムも引数として渡されて「副プログラ ム呼び出し」という処理の対象となることもあるので、何がしかの意味で同じ 扱いのできるという基準でグループ化することにより、副プログラムの型を定 める。現実のプログラミング言語にはその他に多くの型が登場するであろうが、 HIRにない型は、原則として、HIRの型に分解して表現する。 　コンパイラにおける並列化やコード最適化では、配列は重要な対象である。 そのため、HIRの設計では、配列の情報参照や、配列要素の認識に適した表現 形式をとるようにしている。 ３．３　要素的言語機能への分解 　上記のような考えのもとに、入力言語の機能を要素的言語の機能に分解し、 言語依存性の少ない表現に変える。その具体的イメージを把握してもらうため に、C言語を例としてとりあげながら説明する。 （１） 変数とオブジェクトの表現 　変数は一般にはその値を表す場合と、値の入れ場所であるオブジェクトを表 す場合がある。代入演算子(assign)の左辺に（第１子として）くる変数はオブ ジェクトを表現する左辺値(l-value)として扱う。配列要素は、配列修飾演算 子subsで配列指定と添字式を結合して表わす(##14)。構造体型のオブジェク トとその要素名は構造体修飾演算子qualで結合し、ポインタ型の式とポイン ト先要素はポインタ修飾演算子arrowで結合する。 　代入演算子の左辺でない場所で変数への参照を表す左辺値を書くときは、そ の変数の番地（オブジェクトの位置）を求めるaddr演算子を使って左辺値で あることを明示的に示す。配列、構造体、共用体は左辺値として扱う。ポイン タの値も左辺値である。ポインタの指す先のオブジェクトの内容を取り出すに はcontents演算子を使う。配列をその先頭要素へのポインタに変換するには decay演算子を使い、ポインタによる表現を配列に変えるときはundecay演算 子を使う(##11)。 （２）定数　(##11) 　定数としては、整数定数、浮動小数点定数、文字定数、文字列定数、bool 定数などがある。その具体的記述形式は入力言語に依存するが、HIRではその 具体表現の違いにとらわれずに処理できるよう、定数も記号表エントリとして 表現する。 （３）式と文　(##11) 　式は、算術演算子、比較演算子、論理演算子などを定数や変数、式に作用さ せる表現として表す。定数や変数自体も１つの式である。 　文としては、代入文、if文、反復文、switch文、jump文、return文、なら びに複数の文を一まとめにするblock文がある。式を１つの文であるかのよう に扱うexpStmt文もある。 　入力言語において上記では直接に表現できない複合的な意味を表わす式や文 は、これらの基本的な式や文に分解して表現する。 [[ (a) 複合演算子 　Cにおける代入と算術演算を複合した複合演算子は、要素演算に分解して表 す。例えば i++ は i=i+1; と同じ表現にする。これはフロー解析やSSA変換 を単純にするためでもある。複合変数に対する複合演算子の分解においては、 一時変数を導入することもある。 (b) 短絡条件式、?: 演算 　Cの論理演算子の評価は、真偽が判明した時点で後ろの評価をやめるので、 そのことをif文に展開して明示的に示す。?: 演算子で表現された式はif文 に展開するが、真偽が判明した時点で後ろの評価をやめるよう、必要に応じて 入れ子構造にして表す。その際、型変換が必要なら、そのことを型変換演算子 によって明示的に示す。 (c) コンマ演算子、多重代入 　コンマ演算子や多重代入も、言語で定められた評価順序に従って、分解して 表現する。これに伴い、１つの文や式が複数の文に展開されることがある。 (d) 代入式と式のリスト 　式を分解して表現するとき、演算順序をソースプログラムでの指定に合わせ るため、式の因子の部分に代入文を書いた埋め込み代入文を許すことにし、式 として使われる代入文（代入式）の値は、代入文の左辺にある左被演算数に代 入される値であるとする。式のリストを構成したとき、そのリストの値は末尾 要素としての式の値である。 ]] （４） 入口処理、出口処理 　副プログラムの入口は副プログラム定義ノードで表現し、出口はreturn文 で表現する。しかし、入口処理、出口処理の内容は、コード生成部に任せるこ とにし、高水準共通中間表現の段階ではそれ以上分解しない。ただし、副プロ グラム定義ノードやreturn文は、入口、出口処理のうち、言語によらない部 分を表すものなので、明示的に表現し、副プログラムの入口で入力言語固有の 初期設定を要求する場合には、その内容を副プログラム内の処理の一部として、 HIRで記述する。このようにして、言語依存性や機種依存性があまり表面化し ないようにする。　(##11) ３．４　表現例 　HIR による表現の例を示す。ここでは、intは4Bの大きさであるとする。 // はHIRの各ノードに対する行末注釈の始まりを表す。　(##11) /* tpif1.c: if-statement (simple one) */ int a, b, c; int main() { a = 1; b = 2; if (a == 0) c = a; else c = a + 2; return c; } (a) Source program (prog 1 (subpDef 2 void true int> main> (labeldSt 4 void (list 5 ) (block 7 void file tpif1.c line 3 (assign 8 int file tpif1.c line 7 ) (assign 11 int file tpif1.c line 8 ) (if 14 void file tpif1.c line 9 (cmpEq 15 bool ) (labeldSt 18 int (list 19 ) (block 21 void (assign 22 int file tpif1.c line 10 ))) (labeldSt 25 int (list 26 ) (block 28 void (assign 29 int file tpif1.c line 12 (add 31 int )))) (labeldSt 34 void (list 35 ) )) (expStmt 37 int file tpif1.c line 13 (call 38 int (addr 39 true int>> true int> printf>) (list 41 (decay 42 "c=%dエn">) ))) (return 45 int file tpif1.c line 14 ))))) (b) HIR representation (##14) 　図１．HIR によるプログラム表現の例 ３．５　言語の抽象化による言語依存性の隠蔽 　入力プログラム(source program)における処理内容は、機械命令にまで分解 すると入力言語に依存しないものとなるが、そこまで分解しなくても、種々の 手続き型言語に共通する要素的言語の段階で考えるならば、入力言語によらな い表現として記述できる。型などの情報も、基本型や、階層関係、前後関係と いうレベルに分解してしまうと、言語に依存しない形で扱えるものが多い。言 語依存な仕様のうち、処理内容に反映されるものは、要素的言語における処理 命令として表現する。このようにして、言語概念を基本的なものに分解し、抽 象化してゆくと、種々の手続き型言語に共通な表現レベルに達することができ る。ただし、すでに言及したように、言語解析部で作る記号表には言語依存な 部分もかなりある。 　コンパイラのコード量の面で大きい比重を持つ最適化や並列化の処理では、 操作が代入であるか演算であるかなどは頻繁に調べるが、型が何であるかまで は頻繁には調べない。型情報を頻繁に必要とするのは、最後に対象マシンに合 わせてコード生成する時であるが、それも基本型を見れば間に合うことが多い。 コンピュータで実行する処理の内容はHIRで表現され、HIRからは記号表への リンクがあるが、言語解析部より後ろのフェーズでは、処理内容の解析、変換 が中心となるので、記号表の言語依存情報までたどる必要のある場合は少なく、 大部分の処理を言語に依存しない形で行なうことができる。 　プログラムの論理的内容は、言語依存性の低い操作情報を表すHIRと、言語 依存情報を含む記号表に分離できる。配列要素の並べ方のようにパラメータ化 できるものもある。 　　プログラムの論理的表現　＝　　HIR　　＋　　記号表 　　　　　　　　言語依存性　　　　少　　　　　　中 　　　　　　　　機種依存性　　ほとんどなし　　わずか 　　処理の共通化：　表現形式の共通化（要素的操作への分解） 　　　　　　　　＋　依存情報の記号表への隠蔽 　　　　　　　　＋　パラメータ化 そこでは、上記のような、言語概念の基本要素への分解と抽象化によって、言 語依存性を隠蔽でき、言語解析部より後ろの処理の大部分を言語に依存しない 形で実現できる。もちろん、多くの処理を完全に言語に依存しない形で実現で きるというのではなく、言語依存な処理を小さいクラスや手続きに隠蔽するこ とによって、言語間での共用性を増加できるということである。言語概念の基 本要素の抽出にあたっては、現行のすべての言語を対象とするとまとめにくい ので、 　　　C、C++、Java、Fortran、Pascal などの手続き型言語と、それに類似した言語を対象とする。最初に実現するの はC言語のコンパイラである。 　HIRは対象機種には依存しないものであるが、それは生成したHIRを任意の 機種にそのまま移せるということではない。HIRの表現形式自体は機種に依存 しないが、そこで参照する記号表には機種に依存する情報もあり、HIRは記号 表と合わせないと完全なプログラム表現とならないので、Javaのバイトコー ドのように生成されたHIRだけを種々の計算機に持っていって実行できるとい うわけではない。 ３．６　ソフトウェア工学的ツール向け機能 　プログラミング環境などを作る面からは、中間表現と入力プログラムとの対 応がはっきりしていることが望まれる。たとえば、記号の宣言位置であるとか、 式の中間表現に対する入力プログラム上の位置が求まることなどの要望がある。 プログラミング環境ばかりでなく、並列化結果を入力言語と同じ言語で出力す るときも、もとの入力プログラムと対応がよくとれていることが望まれる。 　本プロジェクトの最初のバージョンでは、中間表現と入力プログラムの間で 対応関係が十分にとれるようにするということや、並列化結果が入力プログラ ムとよく対応がとれているということまでは実現しない。ただし、「ある変数 を最初に宣言した行はどこか」とか、文の先頭がソースファイルの何行目かと いうような、比較的容易に実現できる機能についてはある程度実現する。 　プログラミング環境から見て、中間表現と入力プログラムをうまく対応づけ る機能モジュールは、コンパイラ側で実現するよりも、むしろプログラミング 環境開発の一環として実現する方がツールとの整合性等の面でよいと思われる。 コンパイラ側では、そのような機能の拡張や追加が容易なコンパイラ構造にす ることと、ドキュメント整備が重要であると考える。 ３．７　コンパイル処理の進行とHIRの変換 　高水準中間表現は、コンパイル処理の進行に合わせて、次々と変換されてゆ く。C言語の場合、構文解析直後は、++や=+などの複合演算子等を含んだまま の表現形式 HIR-C を経由するが、その後、これらのC言語固有の表現を要素 的言語機能に展開し、言語間共通の表現である本来のHIRに変換する。それを HIR-Cと区別する必要があるときはHIR-base と呼ぶ。 (a) HIR-C Cの構文・意味解析を行った直後のHIRで、 　　　　　　　Cの複合演算子等を含む。 (b) HIR-base Cの複合演算子等を展開し、言語依存性をほとんど 　　　　　　　なくしたもの。単にHIRというときはHIR-baseを表す。 高水準中間表現でのフロー解析や最適化、並列化など、主な処理はHIR-base に基づいて行う。ただし、ソースのイメージを尊重したいソフトウェア工学的 ツールなどでは、HIR-Cを使うこともある。コンパイラでの処理の進展に伴っ て、HIRに種々の情報が付加されたり、変換されたりする。HIR-CもHIR-base も、あるいはHIR-baseの中での種々の段階の表現も、すべて同じHIRの構文 規則に従った形をしている。そのレベルの違いは、ある種のノードが含まれて いるか否か、ある情報が算出されているか否か、などの点で区別される。これ らのレベル間には順序関係があり、フロー解析が終わっていないと並列化に進 めないなどの制約がある。 ４．　記号表 　変数名や副プログラム名、クラス名など、入力プログラムに現れるすべての 記号に対し、その情報を記号表に記載する。その情報が何であるかは、宣言文 やプログラム構造などによって決まるものが多く、構文解析、意味解析のとき に設定されることが多い。定数やコンパイラ内部で生成するレジスタ、一時変 数なども、すべて記号表に記載する。言語解析を行なったあと、最適化やコー ド生成に必要となる主な情報はデータ型である。もう一つの重要な事項である スコープ情報は、言語解析部で処理されるものであり、後段では頻繁には参照 されない。記号表はスコープごとに作られ、内側のスコープの記号表は外側の スコープの記号表の子供として作る。したがって、スコープの階層関係は、 個々の記号表をノードとする木構造として表現される(##11)。 　それ以上分解して表現することをしない基本型(basic type)としては short int, int, long int, long long int, float, double, long double, bool, char, (##14) unsigned short int, unsigned int, unsigned long int, unsigned long long int, unsigned char, offset, void を設け、そのほかに型を構成する型構成子(type constructor)として enumeration, pointer, vector, structure, union, subprogram, typedef を設ける。typedef など、型を定義する言語機能で指定されるユーザ定義型 （defined type）の情報も、型情報として記号表に入れる。入力言語における 型の概念は言語ごとに異なるが、要素型に分解してしまうと言語による差違は あまりなくなり、言語解析部より後ろのフェーズでは、言語にあまり依存しな い形で扱うことができる。しかし、言語依存な部分は少し残るので、それらに 対する処理やパラメータは、SourceLanguageというクラスに局所化する。 　構造体とその要素、クラスとフィールド名やメソッド名などは、記号間の階 層関係とみることができ、同じ構造体に含まれる要素の間の関係、同じクラス に含まれるメソッドの間の関係などは、同類の記号の間の前後関係とみること ができる。これらの関係の認識は、言語解析のときにすべきものであり、それ より後ろのフェーズでは、具体的宣言形式というような言語依存の関係ではな く、階層関係や前後関係など、多くの言語に共通な概念で表現されているとし て扱うことができる。 　演算操作はデータ型によって異なるが、これを細分化してそれぞれを異なる 形式で表すと、表現が煩雑になる。コンパイラ内での処理には、それらを細分 化しなくても可能な処理が多々ある。そこで、中間語の各ノードから記号表の 型情報を参照可能にすることにして、算術演算などの演算子を型で細分するこ とは行わない。 　さきにあげたプログラム例に対する記号表の主要内容を次に示す。 SymTable Root subp main false int> type true int> size 4 SymTable _main1 parent SymTable Root var a 1 int in _main1 var b 2 int in _main1 var c 3 int in _main1 　記号表はデータ構造として表現されるものであるが、テキスト表記も定めら れている。すでに述べたように、１つのプログラムのHIRと記号表を合わせて テキスト表記したものは、高水準中間表現をテキスト表記した中間表現プログ ラムと見なすことができる。 ５．　低水準中間表現 ５．１　計算機の抽象化による機種依存性の隠蔽方針 　低水準の中間表現としては、JavaのbytecodeやPascalのP-codeなど、仮 想的スタックマシンの命令が使われることがある。これらは入力プログラムか らの変換が容易で、対象機種を変更するのも容易なことを特徴とする。しかし、 レジスタが表面に出ていないので、レジスタを有効に利用する最適化処理には 不向きである。また、スタックに対するプッシュやポップを基本命令とするの で、命令の順序を入れ換える最適化やスケジューリングにも不向きである。し たがって、スタックマシンの命令形態は、最適化処理や並列化処理を重視する コンパイラには適さない。 　そこで、低水準の中間表現としては、レジスタを表面に出した抽象レジスタ マシン語の行き方をとる。今後の計算機は多数のレジスタを持つ方向にあるの で、それの有効活用がコンパイラの課題となる。また、プロセッサの内部速度 とメモリの速度とのギャップが大きくなる傾向にあるので、それを埋めるため に、ロード命令やストア命令に対して特別の対処を必要とするようになる。こ のようなことを配慮して、メモリの参照（ロード）と設定（ストア）、レジス タの参照と設定を表面化した仕様を検討するが、複合的な演算の表現や、左辺 値式の多様性、マシンの多様性とコード生成時のパタン照合の容易さ等を考慮 して、それは木構造の形とする。これを低水準中間表現 LIR（Low level Intermediate Representation）と呼ぶ。　(##24) 　LIRにおいて部分木としてまとめる処理は、値を設定するset指定、制御の 流れを指定するjumpとcallのいずれかを高々１つ含むものに限定する。した がって、複合文などは幾つかの部分木に分解する。setにおける設定先はメモ リまたはレジスタであり、演算の対象は、メモリやレジスタ、定数、下位部分 木の演算結果のいずれかである。LIRにおいて、１つの副プログラムは基本ブ ロックを先行・後続関係で接続した制御フローグラフとして表現され、基本ブ ロックは部分木の列（リスト）で表現される。各基本ブロックには、jumpが 含まれるとしても末尾にしか含まれない。　(##24) 　アセンブリ言語では、処理内容ばかりでなく、プログラムで使っている記号 の定義やメモリの使い方の指定なども指定する。LIRでも、LIRのプログラム で使っている記号をモジュールと呼ぶ部分で定義する。　(##24) 　LIRでは機種ごとの特性を反映できるようにするが、パラメータ化やアクセ スメソッド共通化、コード生成のためのマシン記述などにより、最適化や並列 化の処理の多くを機種間で共通化できるようにする。 　　処理内容の表現　＝　LIR　　＋　マシン記述　＋　記号表　 　　　　言語依存性　　　なし　　　　少　　　　　　　中 　　　　機種依存性　　　中　　　　　大　　　　　　わずか 　　処理の共通化：　表現形式の共通化（細部の違いを見なくても処理可能） 　　　　　　　　＋　アクセスメソッドの共通化 　　　　　　　　＋　パラメータ化 　　　　　　　　＋　マシン記述 ５．２　LIRへの変換 (##11) 　LIRは、通常、HIRから変換することによって構成する。LIRはテキスト表 現をもつ１つの言語でもあるので、LIRをテキスト表現またはファイルとして 入力することも可能である。LIRをテキストとしてファイルに出力すれば、プ ログラムをLIRの段階で計算機間で伝達することも可能になる。ただし、LIR の文法は機種非依存であるが、それで表現された具体プログラムには後述のよ うに機種依存性が入るので、上記の伝達は異機種間では可能でない。 　HIRをLIRに変換するのは、HIRを見てLIR全体を新たに生成するのであり、 HIRの一部を書き換えてLIRに変換するのではない。HIRのノードを表すオブ ジェクトとLIRのノードを表すオブジェクトは異なるクラスに属するものであ るが、そこに含まれる変数名など、両者に共通な情報は多くある。HIRもLIR もIR (Internal Representation) というクラスのサブクラスであり、IRクラ スのメソッドは、HIRに対してもLIRに対しても同じ呼出形式と意味で使うこ とができる。したがって、IRクラスのメソッドのみを使った処理は、HIRにも LIRにも適用できる。 　HIRは対象機種に依存しない表現であるが、LIRでは対象機種の特性を表現 可能としている。したがって、HIRからLIRへの変換は、機種特性を表現する マシン記述を参照しながら行なう。LIRの構文とその意味は入力言語と対象機 種によらないものであるが、それで表現したLIRのインスタンスは対象機種に 依存するものである。 　　HIR　　　＋　マシン記述　　　→　　　LIR 　　機種非依存　　　機種依存　　変換　　機種依存 ５．３　LIRの型　(##11) 　LIRで扱うデータの型は整数型と浮動小数点型に大別される。整数型は、I の後ろにビット数をつけて、 　　I1, I8, I16, I32, I64, I128 と表わす。浮動小数点型は、Fの後ろにビット数をつけて 　　F32, F64 と表わす。 　具体的なコンパイラでは、入力言語と対象機種の組み合わせが決まると、上 のような形でデータの型を決めることができる。整数に対して符号つきか符号 なしのいずれの扱いをするかは、演算子で区別する。文字やbool値、ポイン タなどは整数型として表現する。 ５．４　レジスタの機種依存性隠蔽　 　現実の各種の機種を見比べると、大きく異なるものの１つとして、レジスタ の構成や個数、扱い方の違いがある。レジスタを物理的側面から見ると機種に よって大きく異なるが、コンパイラにおける機能的側面から見ると、 　　変数の値を一時的に保持し、後続の処理で利用可能にする演算レジスタ 　　引数の受け渡しに使う引数レジスタ 　　関数の値の返却に使う返却値レジスタ 　　特定目的に使うスタックポインタやフレームポインタなどのレジスタ などに分類できる。もちろん、引数レジスタや返却値レジスタも演算レジスタ として流用できる。また、コンパイラの処理過程では、さらに呼ばれ側待避 （callee save）レジスタ、呼び側待避（caller save）レジスタという区別も 必要になる。最適化や並列化の観点からは、このような分類で処理を共通化で きる。 　レジスタの数は機種ごとに異なるが、LIRではまずその個数を限定しない仮 想レジスタを導入して、それによって処理内容を表現する。コンパイラの終段 では、実レジスタ割付の処理により、仮想レジスタを実レジスタに対応付けて ゆくが、１つの仮想レジスタが同じ実レジスタに対応するとは限らず、一般に は、場所によって異なる実レジスタに対応する。実レジスタ割付は機種依存性 の強い部分であるが、レジスタの生存区間解析や使うレジスタ数を極力少なく する処理など、多くの部分を機種に依存しない形で作ることができる。 ５．５　異なる命令体系間での処理の共通化 　計算機の命令体系は機種毎に異なり、具体的命令の生成や、特定機種固有命 令の有効利用などのためには、機種ごとの処理が必要である。しかし、低水準 中間表現に対する並列化や最適化の処理においては、 　　　ロード命令か 　　　ストア命令か 　　　２つの命令間で演算子と対象データが同じであるか 　　　結果を入れるレジスタやメモリ番地は何か 　　　副作用として設定されるものは何か（条件コード等） 等を見るだけでできることも多く、これらの情報へのアクセスメソッドと結果 の表現形式を同じにしておくと、多くの処理を機種間で共通化できる。 　対象機種の特性をマシン記述として形式的に表現し、LIRの部分パタンがど のような機械命令列に対応するかを与えておく（あるいはそのような部分パタ ンを一部自動生成できるようにする）ならば、パタン照合の技術によって、 LIRを対象機種の機械命令に展開できる。そのパタン照合の処理は機種間で共 通化できる。 　　　　マシン記述（機種特性）、LIRのパタンと機械命令列の対応関係 　　　　　　　　　　　　　　↓ 　　LIRによるプログラム表現　→　パタン照合 　　　　　　　　　　　　　　↓ 　　　　　　　　　　対象機種の命令列 　副プログラムの呼び出し形式は、機種ごと、ABI (Abstract Binary Interface) ごとに大きく異なり、具象マシンを想定すると共通化が困難にな る。そこで、副プログラムの入口処理を prolog、出口処理を epilog という 命令が処理するものとし、その内部処理をLIRでは規定せず、機種固有ルーチ ンで処理することとする。 ５．６　コンパイル処理の進行とLIRの変換 　低水準中間表現も、コンパイル処理の進行に合わせて、次々と変換されてゆ く。すなわち、HIRから変換された直後のものと、仮想レジスタ割付を行った もの、対象機種の機械語命令を表現したもの、実レジスタ割付を行なったもの など、いくつかの段階を踏んで機械語に変換される。 　　　HIRからの変換直後 　　　仮想レジスタの導入 　　　メモリ割付 　　　対象機種の命令対応に展開 　　　実レジスタ割付 　　　アセンブリ言語への変換 　HIRの場合と同様に、これらはすべて同じLIRの構文規則に従った形をして いる。そのレベルの違いは、どこまで細かく分解されているか、ある種のノー ドが含まれているか否か、ある情報が算出されているか否か、などの点で区別 される。 　次に、先のプログラム例に対して、HIRから変換した直後のLIRを例示する。　 (##11) Module "tpif1.c": Global Symbol table: ("memcpy" STATIC UNKNOWN 4 "text" XREF) ("string.6" STATIC A48 1 ".text" LDEF) ("printf" STATIC UNKNOWN 4 ".text" XREF) ("main" STATIC UNKNOWN 4 ".text" XDEF) (DATA "string.6" (I8 99 61 37 100 10 0)) Function "main": Local Symbol table: ("functionvalue.5" FRAME I32 4 0) ("returnvalue.4" FRAME I32 4 0) ("c.3" FRAME I32 4 0) ("b.2" FRAME I32 4 0) ("a.1" FRAME I32 4 0) Control Flow Graph: #1 Basic Block (.L1): DFN=(1,1), <-() ->(#2) (PROLOGUE (0 0)) (JUMP (LABEL I32 ".L2")) #2 Basic Block (.L2): DFN=(2,2), parent=#1, <-(#1) ->(#3,#4) (SET I32 (MEM I32 (FRAME I32 "a.1")) (INTCONST I32 1)) (SET I32 (MEM I32 (FRAME I32 "b.2")) (INTCONST I32 2)) (JUMPC (TSTEQ I32 (MEM I32 (FRAME I32 "a.1")) (INTCONST I32 0)) (LABEL I32 ".L3") (LABEL I32 ".L4")) #3 Basic Block (.L3): DFN=(3,4), parent=#2, <-(#2) ->(#5) (SET I32 (MEM I32 (FRAME I32 "c.3")) (MEM I32 (FRAME I32 "a.1"))) (JUMP (LABEL I32 ".L5")) #4 Basic Block (.L4): DFN=(6,3), parent=#2, <-(#2) ->(#5) (SET I32 (MEM I32 (FRAME I32 "c.3")) (ADD I32 (MEM I32 (FRAME I32 "a.1")) (INTCONST I32 2))) (JUMP (LABEL I32 ".L5")) #5 Basic Block (.L5): DFN=(4,5), parent=#3, <-(#3,#4) ->(#6) (CALL (STATIC I32 "printf") ((STATIC I32 "string.6") (MEM I32 (FRAME I32 "c.3"))) ((MEM I32 (FRAME I32 "functionvalue.5")))) (SET I32 (MEM I32 (FRAME I32 "returnvalue.4")) (MEM I32 (FRAME I32 "c.3"))) (JUMP (LABEL I32 ".L6")) #6 Basic Block (.L6): DFN=(5,6), parent=#5, <-(#5) ->() (EPILOGUE (0 0) (MEM I32 (FRAME I32 "returnvalue.4"))) ６．　フロー解析情報の概要 ６．１　フロー解析情報の種類 　フロー解析は副プログラムごとに行ない、それには制御フロー解析とデータ フロー解析がある。制御フロー解析により、副プログラムを基本ブロックに分 割し、その先行、後続関係を調べて、制御フローグラフ（CFG, Control Flow Graph）を作る。制御フローグラフから、基本ブロック間の支配関係などを求 める。また、ループ情報を別に求めることもある。データフロー情報は、基本 ブロックを単位として算出し、到達可能定義や利用可能変数などの情報、定 義・参照リストなどを求める。データフロー情報は主として各々の基本ブロッ クに対する情報として表現する。 　　　制御フロー情報 　　　　　制御フローグラフ（基本ブロックの先行・後続関係） 　　　　　支配関係、他 　　　データフロー情報 　　　　　到達可能定義、利用可能変数、利用可能レジスタ、 　　　　　変数やレジスタの生き死に状態、定義・参照リスト、他 　　　ループ情報 　　　　　ループの入れ子関係、ループを構成する基本ブロックのリスト、他 ６．２　中間表現とフロー情報との対応付け 　フロー解析は中間表現に対して行なう。HIRからはHIRのフロー解析情報が 得られ、LIRからはLIRのフロー解析情報が得られる。フロー解析情報は、中 間表現に対する最適化や並列化の際に利用する。順序としては、制御フロー解 析を行なったあと、データフロー解析を行なう。HIRとLIRのフロー解析のい ずれか一方のみ、あるいは両方を行なうこと、フロー解析の特定項目を選択的 に実行することなども可能である。ただし、それらの項目の間には、Aの項目 が実行されていないとBの項目が実行できない、などの依存関係がある。フロ ー情報は副プログラムごとに算出される。　(##11) （１）HIRとフロー情報の対応付け 　１つの副プログラムの制御フローは基本ブロックのグラフとして表現し、そ の制御フローグラフは、副プログラム記号からも参照できる。制御フロー情報、 データフロー情報は、基本ブロックのグラフから参照できるが、プログラムの 中間表現を見ながら注目点がどの基本ブロックに含まれるかを知ることや、基 本ブロックが中間表現のどこに対応するかを知ることができるように、中間表 現と制御フローグラフの間で相互にリンクを張る。入力プログラムでラベルの 付いた文は基本ブロックの開始点とみなす。選択文、反復文など、幾つかの基 本ブロックに分解される文や式では、基本ブロックの先頭に必要なら内部ラベ ルの定義点を設け、基本ブロックの開始点であることを明示する。基本ブロッ クの開始点に入力プログラムでラベルが付けられていれば、内部ラベルは生成 しない。これらのラベル定義点から基本ブロックの情報へのリンクが張られる。 逆に、基本ブロックからはその先頭に位置するラベル定義点へのリンクが張ら れる。 　プログラム変換の過程で、ある制約の範囲内で、備え付けのメソッドを使っ て基本ブロックのグラフや処理内容を変更すると、HIRの内容がそれに連動し て変更される。したがって、その制約の範囲内では、フロー情報を見ながら１ つの変換を行ったあとも、再びHIRをベースにして他の解析や変換を行うこと ができる。逆に、HIRを変更すればフロー情報は無効になってしまうので、変 更後にフロー情報を必要とする場合は再計算する（##21）。 （２）LIRとフロー情報の対応付け　(##21) 　LIRは部分木のリストとして表現され、それが基本ブロックごとにまとめら れ、先行、後続関係で結合されている。すなわち、LIRは部分木のリストとし て表現された基本ブロックの制御フローグラフとして表現されている。したが って、LIRではフロー解析のときに基本ブロックに分割する処理は不要である。 jumpや分岐はLIRの命令として表現されており、基本ブロックを接続する辺 によって暗黙的に表現されているのではない。 　LIRでは、HIRのように１つの文がいくつかの基本ブロックに分解されるこ とはないので、このように基本ブロックを単位とするフローグラフそのものを LIRの表現とすることが可能である。 （３）フロー情報の例　(##11) 　先のプログラム例に対するHIRに基づくフロー解析情報の要点を次に示す。 (a) 制御フロー情報 Control flow analysis of main [Basic Block] BB =1 (ENTRY BLOCK) Succ(2,3) Pred() Stmt( assign 4 assign 7 cmpEq 11) BB =2 Succ(4) Pred(1) Stmt( assign 17) BB =3 Succ(4) Pred(1) Stmt( assign 23) BB =4 (EXIT BLOCK) Succ() Pred(2,3) Stmt( labeldSt 28 BBlock 4 return 30) [ImmediateDominator] BB =1 ImmediateDominator=NULL BB =2 ImmediateDominator=1 BB =3 ImmediateDominator=1 BB =4 ImmediateDominator=1 [ImmediatePostDominator] BB =1 ImmediatePostDominator=4 BB =2 ImmediatePostDominator=4 BB =3 ImmediatePostDominator=4 BB =4 ImmediatePostDominator=NULL (b) データフロー情報（一部） BBlock 3 _lab4 def assign 23 kill assign 17 reach assign 4 assign 7 defined _xId7(c) used a exposed _xId4(a) _xId8 eGen _xId4(a) _xId8 eKill _xId7(c) availin _xId4(a) _xId6 availOut _xId4(a) _xId6 _xId8 liveIn _xId4(a) _xId8 liveOut _xId7(c) defIn _xId4(a) _xId5(b) defOut _xId4(a) _xId5(b) _xId7(c) defNodes var 24 c useNodes var 26 a defUseLists of main b _xId4(a) defined at var 5 a used at _xId5(b) defined at var 8 b used at a _xId7(c) defined at var 18 c used at defined at var 24 c used at c ６．３　フロー解析の共通化 （１）フロー解析情報の算出 　データフロー解析の際、各々の変数や部分式に識別用の番号を付与し、HIR やLIRにおける定義点、参照点のノードにも識別用の番号を付与し、それらの 識別番号によってデータフロー情報を参照する。HIRとLIRでは、フロー情報 の内容は異なるが、番号表現することによって、HIRとLIRでのフロー解析プ ログラムは、大部分、共通化できる。 　制御フロー情報、データフロー情報は、フロー解析モジュールによってHIR またはLIRから算出する。フロー解析モジュールは、HIRまたはLIRからの情 報収集部とデータフロー方程式等を解く解析部からなり、解析部はHIRとLIR で共通化する。 　　フロー解析モジュール　＝　情報収集部　＋　解析部 　　　　　　　　　　　　　　HIR用、LIR用　　　共通 （２）フロー解析とプログラム変換 　フロー解析は、HIRをLIRに変換したときや、並列化や最適化のために大き いプログラム変換を行なったあとでは再計算する。プログラム変換の過程でフ ロー情報を逐一更新することは要求しない。ただし、１つの変換モジュールの 中でその変換に使うフロー情報を更新する必要があれば、それはその変換モジ ュールの中で更新する。 　　　　HIR生成（フロント） 　　→　HIRフロー解析 　　→　HIR並列化、最適化変換１ 　　→　HIRフロー解析 　　→　HIR並列化、最適化変換２ 　　→　… 　　→　HIRからLIRへの変換 　　→　 LIRフロー解析 　　→　LIR並列化、最適化変換１ 　　→　 LIRフロー解析 　　→　LIR並列化、最適化変換２ 　　→　… 　　→　 LIRフロー解析 　　→　コード生成 　並列化や最適化の指示情報など、後ろのフェーズへ渡すべき情報は、フロー 解析をやりなおしても、前で求めた情報を伝達できるようにする。 （３）プログラム変換 (a) HIRに対する変換 　HIRに対して、並列化や最適化のために行なう変換は、部分木やリーフを変 換単位とするものであり、 　　　リーフを別のリーフに置き換え（ソース変数名の一時変数への変更等） 　　　部分木を別の部分木に置き換え（簡略化や展開） 　　　部分木をリーフに置き換え（式の一時変数化（レジスタ化）等） 　　　リーフを部分木に置き換え（変数ロードの計算式への変換等） 　　　部分木のコピー（リーフも） 　　　文の挿入、削除 　　　１つのノードへの枝の追加、削除 　　　ノードの挿入（ラベル等） などである。これらの操作を行なうためのメソッドを用意するので、それらを 使って許される変換を行なう。ノード単位で操作することもできるが、その際 は、HIRの木構造の構成をよく心得て行う必要がある。制御構造を変更する変 換を行なった場合は、制御フロー解析とデータフロー解析をやりなおす。 (b) LIRに対する変換 　LIRは部分木の列なので、 　　　部分木単位の追加、挿入、削除 　　　部分木の列を単位とした追加、挿入、削除 　　　１つの部分木の部分木列への展開 ならびに 　　　部分木に対するHIRと同様の変換 を行なうことができる。LIR自体がすでに基本ブロックを単位とする制御フロ ーグラフとして表現されているので、基本ブロック間の接続関係を変更しない 変換に対しては、支配関係等を求める制御フロー解析を再実行する必要はない が、LIRを変更した場合、データフロー解析は再実行する必要がある（##21）。