2003/12/8, 2004/4, 5/22, 6/12, 8/19 ＩＩ．　高水準中間表現の概要 　　　　　　　　　　　　　　　　　　(##24)：2004/ 5-6月改訂 　　　　　　　　　　　　　　　　　　(##23)：2004/ 4月改訂 　　　　　　　　　　　　　　　　　　(##22)：2003/ 7月改訂 　　　　　　　　　　　　　　　　　　(##21)：2003/ 6月改訂 　　　　　　　　　　　　　　　　　　(##14)：2002/ 6月改訂 　　　　　　　　　　　　　　　　　　(##11)：2002/ 1月改訂 　　　　　　　　　　　　　　　　　　(##10)：2001/ 11~12月改訂 　　　　　　　　　　　　　　　　　　(##9) ：2001/ 10月改訂 １．　概要 （１）言語の抽象化 　高水準中間表現 HIR (High level Intermediate Representation) は、Cや C++、Java、Fortran、Pascalなど、現行の手続き型言語における処理内容の 表現を抽象化したものである。手続き型言語における各種の概念は多岐にわた るが、処理の表現について見ると、算術式や選択文、反復文など、共通する概 念がある。その表現形態は言語によって異なるが、それらを分解してゆくと機 械命令の列になり、言語依存性はなくなる。そこまで分解するのでなく、手続 き型言語の要素的概念のレベルまでに留めるならば、プログラミング言語の概 念と１対１に近い対応関係があり、しかも言語依存性のない表現として抽象化 することができる。そして、いくつかの細かい点を例外扱いすると、次のよう な変換を行なうことができる(##10)。 　　入力言語　　　　　　　ーー　言語固有の諸概念 　　　｜　　　　　　　　　　　　言語依存、機種非依存 　　　↓ 　　高水準共通中間表現　　ーー　言語の要素的概念 　　　｜　　　　　　　　　　　　言語・機種非依存 　　　↓ 　　低水準共通中間表現　　ーー　計算機の抽象化 　　　｜　　　　　　　　　　　　言語非依存、機種には部分的依存 　　　↓ 　　機械語　　　　　　　　ーー　操作命令列 　　　　　　　　　　　　　　　　言語非依存、機種依存 　プログラミング言語には、初期のFortranのように階層を持たない言語から、 オブジェクト指向などの概念によって幾つもの階層を持つ言語まで、種々様々 の形態があり、言語全体を見ると共通化はむずかしいように思われる。しかし、 処理内容の表現という観点に絞って見ると、次のように、共通の要素的概念が 見えてくる。 　プログラムは、一般に、幾つかの副プログラム(subprogram)からなり、その うちの１つが主プログラムとして最初に起動され、そこから副プログラムが呼 び出される。１つの副プログラムが起動されると、その中の実行文 (executable statement)が実行される。実行文には代入文(assign statement) や選択文(if statement, selection statement)、反復文(loop statement)、 呼び出し文(call statement)、復帰文(return statement)などがあり、それら の実行過程で、演算のための算術式(arithmetic expression)などが評価され る。選択文や反復文では、判定を行なうための比較式(comparison expression)や論理式(logical expression)が評価される。算術式は加減乗除 などの演算(operation)を表し、比較式は大小比較や等不等比較などを表し、 論理式は論理和(logical or, bitwise or)や論理積(logical and, bitwise and)、否定(negation)などを表す。 　演算対象は変数(variable)や定数(constant)、ならびに式(expression)など である。変数には、単一のデータを表すスカラ変数や、複合されたデータを表 す集成体（aggregate）としての配列(array, vector)、構造体(structure)な どがある。変数参照の方法としては、単純変数名(simple variable name)、配 列要素(array element)、構造体要素(structure element)、共用体要素(union element)、ポインタ参照(pointed element, pointed location)などがある。 スカラのデータ要素が何を表すかは、その要素の型(type)で表現される。その 具体表現は言語や機種に依存するが、コンパイルの過程を見ると、最初の言語 解析の時と最後のコード生成ではデータ要素の具体表現に深く依存した処理が 要求されるが、途中の段階では、多くの処理は演算対象の具体表現に依存しな い形で実行可能であり、細部を隠蔽したままの表現形式で処理可能なものが多 い。 　このような考えに基づいて、高水準共通中間表現の具体仕様を定めてゆく。 それは１つの中級言語を設定することに相当する。その具体表現はテキストあ るいは木構造(tree structure)の形をとる(##14)。木構造として見る場合、 HIRは，節（nonleaf）を表すノード(node) 　　　（演算子　属性　オペランド１　オペランド２　…） と葉（leaf）を表すノード 　　　<記号種別　型　記号> ならびに空記号nullを基本構成要素とする。テキスト表現は、木構造と１対 １に対応し、上記のように、節を 　　　（演算子　属性　オペランド１　オペランド２　…） 葉を 　　　<記号種別　型　記号> と記述する(##14)。木の枝の高さ（深さ）は括弧の入れ子の深さで示される。 木構造と対応しやすくするため、入れ子の深さをインデンテーションの深さで 示すこともある。ここで、オペランド１、オペランド２、…は木の節または葉 であり、葉は記号表に入れた記号またはnullを表す。演算を表す式などは、 このような部分木として表現する。属性は後で述べる型などの情報を表すもの で、その多くは記号表(symbol table)に記載されており、HIRの表現としては、 記号表の記載項（エントリ）を示すにとどめるものが多い。したがって、詳細 な記述としては記号表と合わせて見なければならない。大雑把に言うと、実行 文等における演算や操作の内容とプログラム構造はHIRとして表し、宣言文等 における記号の構造や属性(attribute)は記号表で表すのである。　(##10) 　　プログラム表現　＝　高水準中間表現　＋　記号表 　　　　　　　　　　　　　処理内容　　　　　記号の表現対象の 　　　　　　　　　　　　　　　　　　　　　　構造、相互関連、属性 　記号表は、 　　　（SymTable 　　 　（記号種別　記号名　記号属性１　記号属性２　…） 　　 　（記号種別　記号名　記号属性１　記号属性２　…） 　　　　…　） で表され、記号属性は 　　　（属性名　情報１　情報２　…） で表される(##10)。ただし、デバッグ出力では、改行や記述位置に意味を持た せることにより、記号種別や属性名を一部省略した簡略表現をとる(##14)。 　高水準中間表現の作成や参照は、すべて HIR に対するアクセスメソッドを 介して行ない、記号表の作成や参照はすべて記号表のアクセスメソッドを介し て行なう。 　入力プログラムをHIRに変換するとき、途中で入力言語に固有の表現を含む 中間表現を経由してから、入力言語に依存しないHIRに変換することがある。 たとえばC言語からHIRに変換するときは、一部にC固有の表現を含むHIR-C という中間表現を経由してから共通のHIRの表現に変換する。HIRと言えば通 常は言語固有の表現を含まない共通の表現のことを表す。このことを区別する 必要があるときは、それをHIR-baseと言い、HIR-Cなどと区別して説明する。 なお、特定言語や特定機種について、例を示したりして説明する場合は、その 部分を[[ ]] で囲んで示す。　(##10) （２）言語の抽象化のレベル　(##10) 　言語の抽象化には、構文のみを指定してその意味は入力言語ごとに定める行 き方や、機械語に近いレベルにまで分解して意味付けも細部まできっちり行な う行き方など、種々の方法がある。HIRでは、並列化の結果を入力言語と同じ 言語で出力するなどの使い方にも便利なように、あまり分解しすぎないレベル にとどめる。また、フロー解析や最適化変換、並列化変換などの処理をできる 限り言語や機種によらない形で共通化できるようにすることを意図する。その ために、このような解析や変換を可能とするための意味付けや実行順序の規定 も盛り込むことにする。ただし、それらを完全に微細なレベルまで可能にする ことはLIRに譲り、かなり多くの処理が共通化できればよしとする。HIRにお ける言語の抽象化はこのような考えに基づいて行なっている。 （３）型との対応付け 　HIRの各ノードには、それが値(value)を持つものであればその型を付記す る。したがって、定数や変数、演算式などを表すノードには、すべてその型が 付記される。値を持たないノードには型voidを付記する(##9)。値を格納する 記憶場所をオブジェクトと言い、オブジェクトを表す式を左辺値（l-value） と言う。式の型とはその式の評価結果の型である。型の表し方については別の 章を参照されたい。部分木の型はその部分木(subtree)の根(root)の属性とし て表現する。 [[ 　C言語の表現 int i; float x, y[10]; ... x = y[i] + 1.0; において、代入文のHIRは次のように表わされる。あとで述べるように、 はxxxを要素の型とするベクタ（配列）を意味する。nは配 列要素の数、lbは添字の下限値である。　(##14) (assign float (conv float (add double (conv double (subs float y> ) ) 　　　　(##14) ) ) ) ]] 　ノードには注記（annotation, inf）や種々のフラグを属性として付けるこ とができる。フラグの１つに、その式が定数式であるか否かの表示がある。 （４）付加情報　(##14) 　HIRの各ノードには、型のほかに、必要に応じて付加情報をつけることがで きる。１つの方法として、 InfNode を付けると、その内容は自由に定めることができるので、任意の情報を記入す ることができる（getInfNode(), attachInf()）。それは全部のノードにつける のではなく、必要なものに対してのみ付けることができる。最適化や並列化な どで目的に応じてその内容を決めればよい。 　文のノード（Stmt）には、入力プログラムにおいてその文の先頭を含むファ イル名と行番号を記録することができる（getFileName(), getLineNumber()）。 　もう１つの方法として、true, falseを表わすフラグをいくつか任意のノー ドに付けるメソッドが用意されている（getFlag(), setFlag()）。フラグの種 類はHIRインタフェースで定める。 （５）演算順序と結合順序 　演算の順序(order)は、原則として、木構造を深さ優先で左から右へ（第１ 子、第２子、…）という順番でたどる時の順序に従うが、あとで個別表現の項 で述べるように、いくつかの例外がある。HIRの木構造を構築するとき、入力 言語の文法で規定された評価順序とHIRの構文規則をつきあわせて、どのオペ ランドをどの枝につけるかを決める。評価順序が入力言語の文法で決められて いない部分に対しては、処理系依存であり、コンパイラ開発者の判断による順 序で木構造を組み立てる。この順序は決して変更してはいけないということを 意味するのではない。同じ演算結果を保証できる場合や、言語仕様で許されて いる範囲内では、コンパイラの中で変更してもよい。　(##22) 　演算の結合順序に関しては、 　　　a + (b - c) と 　　　(a + b) - c は数学的には等しいが、有限の桁数で計算するコンピュータでは異なる結果を 生ずることもある。このような問題を避けるため、ソースプログラムで指定さ れた括弧を尊重して、通常は括弧内のものと括弧外のものを結合することはし ない。コンパイラによっては、括弧にとらわれずに結合順序を変更する最適化 変換が指定可能なものもあるが、そのようなコンパイラでも、括弧を無視する と結果に大きな影響が及ぶ場合は括弧を尊重することが要求される。それを実 現可能にするため、ある部分木にencloseという演算子をかぶせると、その部 分木に関しては、結合順序の変更を伴う最適化変換は行なわないことを要請す る。　(##23) 　最適化を行なうと演算の順序が変わったり、一部の演算が削除されたりする。 ある部分に対してはこのような変換を行なってほしくない場合もある。HIRに 対する変換に制限を課する方法として、その範囲にある部分木の根に対して、 setFlag(HIR.FLAG_NO_CHANGE, true) を呼ぶと、その部分木全体に対して最適化変換を抑制する指定をしたことにな る。encloseは結合順序を変えない最適化変換を許すのに対して、 FLAG_NO_CHANGEはその部分木に対するすべての最適化変換を禁止することを 表す(##23)。 （６）HIRのメソッド　(##11) 　HIRにどんなメソッドがあり、どのような仕様になっているかは、本仕様書 では記述していない。それらについてはインタフェースIR.javaとHIR.java を参照されたい。HIRのインスタンスを作るメソッドはHIRインタフェースに 用意されており、newで作る必要はない。記号に関するメソッドについてはイ ンタフェースSym.javaを参照されたい。記号のインスタンスを作るメソッド はSym.javaに用意されており、newで作る必要はない。 　インスタンスをnewで作ることを禁止しているわけではないが、HIRや記号 のインスタンスをnewで直接に作るときは、そのための約束事を十分理解して 作らないと、相互関連に不具合が生ずるおそれがある。インスタンスを作るの にnewを直接に使わないもう１つの理由は、入力言語（や対象機種）の変更、 あるいは機能拡張等にともなってサブクラスを設けると、サブクラスのインス タンスを生成することが必要になり、newを直接使っているとその変更箇所が あちこちに分散して多数になってしまうが、上記のようにすると、変更箇所は HIR.java, Sym.javaの実現部にとどまり、少しの修正ですむためである (##14)。 　HIR.javaやSym.javaには、HIRやSymの属性や下位要素を参照ないし設定 するメソッドもある。そこに書かれたメソッドだけではできない操作について は、HIRやSymの下位のインタフェースを参照されたい。下位のインタフェー スから先に見ると、上位のインタフェースですでに用意してある操作を自分で （首尾一貫しない形で）作ったりすることになる。おもな下位インタフェース としては HIR Stmt.java　　　　　　文 AssignStmt.java　　代入文 LoopStmt.java　　　ループ文 Exp.java　　　　　　式 SymNode.java　　　　記号ノード VarNode.java　　　変数ノード Sym Type.java　　　　　型 Subp.java　　　　　副プログラム Var.java　　　　　変数 Const.java　　　　定数 などがある。メソッドの実現内容を調べるには下位のクラスから見るのもよい が、使い方を調べるには上位のインタフェースから見るようにしないと、混乱 し、使い間違う恐れが多分にある。 （７）HIRの変換　(##24) 　コンパイラ内部では、最適化や並列化などのためにHIRを変換する。その変 換には copyWithOperands, replaceThisNode, deleteThisStmt などの備え付けメソッドを使う。変換によって１つのノードが複数の親からリ ンクされると木構造でなくなるので、そのような誤った変換をさけるためには、 枝をつけかえるのではなく、部分的コピーなどによって新しい部分木を作り、 それを親に接続するようにするのがよい。 　また、変換によって、ループやifなどの制御構造がHIR本来の意味と相容 れないものとならないようにしなければならない。ループに対してはその実行 モデルに合った変換でなければならないし、ifに対してはifの実行モデルに 合った変換でなければならない。たとえば、ループの実行モデルと相容れない 形でループ外からループ内へ飛び込んだり、ループステップ部から飛び出した りすること、ifの実行モデルに合わない形でifのthen部やelse部に飛び込 むことなどは避けなければならない。そのような変換を行った場合は、以後の 処理に破綻を来す場合がある。 （８）HIRノードの番号付け　(##23) 　最適化処理や中間表現の表示の際、ノードの各々に番号がついていた方がよ いことが多い。そのため、HIRを完成させたときに、１つのコンパイル単位、 あるいは１つの副プログラムに対して、その（部分）木の各ノードに一連番号 を付与する。最適化などのためにHIRを変換した場合は、１つの副プログラム の変換が完了した時点で、そ副プログラムの部分木に対して一連番号を付与し なおす。この番号付けはsetIndexNumberToAllNodeというメソッドを部分木に 作用させるとできる。 ２．　HIRのクラス階層 　Javaのようなオブジェクト指向言語をコンパイラ記述言語として選ぶと、 何をクラスとしてとらえるかが重要な設計項目となる。高水準中間表現では、 副プログラムや文、式などのプログラミング言語の概念に対応させたクラスを 設けることを１つの基本方針としている。ただし、ここで言う文や式は、必ず しも特定の言語に忠実な表現ではなく、先に述べたように、具体的言語を要素 的概念に分解して構成しなおした要素的言語における概念を表すものであるが、 それらは元の言語とほぼ対応付けできるものである。木構造の基本構成要素に は、子供のノードを持つ節としてのnonleafノードと、子供を持たない葉とし てのleafノードがあり、その構文をBNFで表すと、nonleafはnonterminal に、leafはterminalに対応する。 　HIRの具体的クラス階層を次に示す。ただし、実装ではこれらの名前は interfaceとしての名前であり、それらを実現するクラスの名前はその名前の 後尾にImplをつけたものになっている(##10)。// はこの仕様記述における行 末注釈の始まりを示す。 IR |- IR_factory // IR object creation factory. |- IrList // List of indefinite number of objects. | |- HirList // IrList whose elements are HIR objects. //##12 | |- LIR // Low level Intermediate Representation | |- ... | |- HIR // High level Intermediate Representation. | // Usual operations on HIR are done by using HIR methods. | |- Program // Program definition node. |- SubpDefinition // Subprogram definition node. |- HirSeq // Sequence of definite number of | // HIR objects. |- HirList // IrList whose elements are HIR objects. | // (Multi-inheritance of interface) //##14 |- Stmt // Statement | |- LabeledStmt // Labeled statement. | |- AssignStmt // Assignment statement. | |- IfStmt // If-statement. | |- JumpStmt // Jump (goto) statement. | | // (Jump unconditionally) | |- LoopStmt // Loop statement. | | |- ForLoop // For-loop. | | |- WhileLoop // While-loop. | | |- RepeatLoop // Repeat-while-true loop. | | |- IndexedLoop // Loop with index range | | // (such as Fortran DO loop). | |- ReturnStmt // Return statement. | |- SwitchStmt // Switch (case) statement. | |- BlockStmt // Block representing a sequence | | // of statements. | |- ExpStmt // Expression treated as a statement. | | // Call statement is treated as an | | // expression statement of function call. | | // Loop start condition expression has | | // label and treated as ExpStmt. | |- InfStmt // An information node | | // which can be treated as a statement. | | // (pragma, comment line, etc.) | |- SetDataStmt // Statement to specify initial data which | // may be set before starting execution. | // //##24 |- LabelDef // Label definition node. // |- InfNode // IR information node. //##17 DELETED. | // Use InfStmt. // | // (pragma, comment line, etc.) |- Exp // Expression |- ConstNode // Constant node |- SymNode // Symbol node | |- VarNode // Variable name node. // | | |- ParamNode // formal parameter name node // | | | //##16 DELETED | | |- ElemNode // struct/union element name node | | //##16 not DELETED | |- SubpNode // Subprogram name node. | |- LabelNode // Label reference node. | |- TypeNode // Type name node. | |- SubscriptedExp // Subscripted variable. |- PointedExp // Pointed object. |- QualifiedExp // Qualified variable. |- FunctionExp // Function call expression. |- PhiExp // Phi function used in SSA |- ExpListExp // Expression representing a list of | // expressions. //##24 |- NullNode // Null (no-operation) node ３．　高水準共通中間表現の構文 　本編では、おもにHIRの構文について説明する。HIRの意味については 　　　高水準中間表現の型と意味 の仕様書を参照されたい(##14)。 （１）HIRの木構造表現 　HIRでは、１つのコンパイル単位全体を１つの木構造で表す。それは、一般 に、初期設定を表す部分木と、副プログラムを表す幾つかの部分木からなる。 副プログラムを表す部分木は、その中における初期設定を表す部分木と実行文 や式を表す部分木からなる。実行文としては、代入文、選択文、反復文、副プ ログラム呼び出しなどがあり、式には算術式や比較式、論理式などがある。部 分木の節は演算子（オペレータ）を表し、葉は変数名や関数名、定数など、記 号表に記載された記号を表す。すでに述べたように、この木構造にはそれと１ 対１に対応するテキスト表現がある(##14)。 　実行可能な木構造の実行（評価）順序については、各々の項で説明する。説 明のない項では、原則として、その木構造を第１部分木（左部分木）から先に、 深さ優先でたどった時の順序と同じである(##10)。部分木をたどるには、通常、 それ用のイテレータを使う(##9)。 　HIRからフロー情報へのリンクは、ラベル定義ノードを介してなされる。入 力プログラムにおけるラベル付きの文は新しい基本ブロックの先頭の文として 扱う。入力プログラムでラベルが定義されていなくても、基本ブロックの先頭 になるノードに対しては、コンパイラで生成する内部ラベルの定義ノードを挿 入する。このようにして、全部の基本ブロックにラベル定義ノードを対応させ、 そこからフロー情報へのリンクを張る。内部ラベルの定義ノードなどを見たく ない場合は、走査のときにそれをスキップする機能を持ったイテレータのメソ ッドを使えばよい。 （２）HIRのテキスト表現　 　木構造のノードには、それが何のノードであるかを表すコードがついており、 型を表す属性もついている。その他の属性がつくこともある。このコードは先 に述べた演算子をコード化したものである。HIRの表現としては、その構文を 表す場合と、HIRで表現された具体的な部分木（HIRのインスタンス）を表す 場合がある。以下の構文記述においては、ノードのコードをxxxCodeの形で表 し、インスタンス記述では、簡潔にするため、xxxCodeを演算子とするノード を単にxxxと表す。Typeはその部分木の表す式や文などの型を表す属性であ るとし、構文としては記述しないが、インスタンスでは記述する。HIRのイン スタンスのテキスト表現のことをそのインスタンスの表記と言い、その表現形 式を表記形式と言う(##10)。 　nonleafノード xxxNode / | ... エ child-1 child-2 .. child-n の構文は、テキストとしては (xxxCode child-1 child-2 ... child-n) と表し、そのインスタンスは、型も付記して 　　　(xxx Type child-1 child-2 ... child-n) と表す。leafノード xxx z の構文は、テキストとしては 　　　 と表し、そのインスタンスは型を付記して 　　　 と表す。leafとnonleafを区別しやすくするため、nonleafでは丸括弧 ( ) を使い、leafでは三角括弧 < > を使うが、見やすさにこだわらない場合は、 三角括弧をすべて丸括弧に置き換えても差し支えない。　(##11) 　たとえば assign / エ x add / エ y 1 という具体例は、テキストとしては (assign int (add int ) ) のように表す。 （３）記法 　中間表現の木構造の各ノードは、第１子として何をとり、第２子として何を とる、… ということを正確に表現するために、中間表現の構文をBNFで記述 する。そのBNF表現におけるいくつかの記法を定める。 　　小文字で始まる英数字列：　終端記号 　　大文字で始まる英数字列：　非終端記号 　　　「 _ 」で終わらない非終端記号： 　　　　　　　記号類を表すクラス名またはインタフェース名 　　　「 _ 」で終わる非終端記号： 　　　　　　　クラス名でもインタフェース名でもない非終端記号で、 　　　　　　　BNF記述を読みやすくするために導入したもの 　　IrList of xxx: xxxを要素とするIrList　(##10) 　属性としては、主要なもののみを示す。後ろに@がついているものは木構造 の枝となるものであり、@のついていないものは枝としてではなく、属性とし て付与されている情報である。（@はデータ構造などとして実体の存在する文法 記号ではなく、あいまいさをなくするための単なる表示上の記号である。 (##11)） Note: Following items are not represented as a subtree dangling to a node but are represented as information attached to the node. They are not traversed when HIR tree is traversed but can be get by applying corresponding HIR methods to the node. Operation code (xxxCode) Symbol table entry (xxxSym) Constant symbol (xxxConst) Symbol table (SymTable, GlobalSymTable_, LocalSymTable_) attr (attribute such as node type which is a symbol representing the type of the result of HIR subtree.) Items represented as a subtree is indicated by @ to clarify. (@ is not a syntactic component but a postfix marker to decrease misunderstanding.) 　このBNF表現における終端記号には、演算子とそれ以外の記号がある。演算 子以外の終端記号は木構造の葉となるものであり、次のものがある。ここで、 xxxSymは記号表に記載された種類xxxの記号を表し、xxxConstは記号表に記 載されたxxx型の定数を表す。 xxxCode: operation code xxx xxxSym : symbol recorded in the symbol table progSym : program name symbol subpSym : subprogram name symbol varSym : variable name symbol (including array/struct/union name symbol) paramSym: formal parameter name symbol elemSym : struct/union element name symbol // fieldSym: field name symbol of a class // classSym: class name symbol labelSym: label name symbol typeSym : type name symbol xxxConst: constant recorded in the symbol table intConst : integer constant (int/short/long/unsigned int/ ...) floatConst : floating constant (float/double/ ...) charConst : character constant (signed/unsigned) stringConst: character string constant boolConst : boolean constant (true is 1, false is 0 in integer) intConstValue: integer constant (not a symbol table entry but value itself). stringConstValue: string constant (not a symbol table entry but value itself). null : empty (nothing, epsilon) NullNode : a leaf node with operation code null. (It is not null.) // (##22) List_of_xxx: java.util.List with elements xxxx. (##10) 　演算子については、加算を表すaddはaddCodeと書くというように、xxxと いう演算子は構文規則ではxxxCodeという形で表現されている（これもあいま いさをなくすための単なる表示上の区別である）。 　各ノードにつける型は、HIR生成時に言語仕様に従って決定する。型の不要 な部分木では型をvoidとする。 　上に述べた仕様書での記述形式とクラス名、インタフェース名、インスタン ス出力時の表記形式との関連を例示する。これらの記号の実際のコーディング 形式については、Sym.javaで宣言した定数を参照されたい。　(##11) インタフェース名　コード　　　　表記形式　クラス名　　　(##11) Program progCode prog ProgramImpl SubpDefinition pubpDefCode subpDef SubpDefinitionImpl AssignStmt assignCode assign AssignImpl IfStmt ifCode if IfStmtImpl VarNode symCode var VarNodeImpl LabelNode symCode label LabelNodeImpl ConstNode constCode const ConstNodeImpl Exp addCode add ExpImpl Exp multCode mult ExpImpl ... ... ... ... （４）HIRの構文 　以下に、高水準中間表現の構文をBNFで表す。ここでは、型は付記していな い。// はこの仕様記述における行末注釈の始まりを示す。構文規則で HIR-C only と示した部分は、HIR-Cにのみ含まれる表現を示す。 Program -> // Program represents a compile unit. ( progCode attr // GlobalSymTable_ // Global symbols of the program ProgSym_ @ // Program name (may be null). InitiationPart_ @ // Initial value specification. SubpList_ @ ) // Subprogram definition list. ProgSym_ -> ( symCode attr progSym ) // Program name symbol. | null GlobalSymTable_ -> // Global symbol table of the program. SymTable // As for SymTable, see Sym and SymTable. | null InitiationPart_ -> // Initial value specification (##14) InitiationBlock_ | NullNode InitiationBlock_ -> // Block containing initiation statements. ( blockCode attr InitiationStmtSeq_ @ ) InitiationStmtSeq_ -> // Sequence of initiation statements InitiationStmt_ @ InitiationStmtSeq_ @ | null InitiationStmt_ -> // Initiation statement ( setDataCode attr // with Exp_l_: l-value Exp_l_ @ ValueSpec_ @ ) // ValueSpec_: constant Exp. | AssignStmt ValueSpec_ -> ConstNode // Constant value | ( listCode attr // List of ValueSpec_ List_of_ValueSpec_ @ ) | ( repeatCode attr // Expression to represent repeating ValueSpec_ @ intConst @ ) // ValueSpec_ intConst-times. SubpList_ -> ( listCode attr // Subprogram definition list List_of_SubpDefinition @ ) SubpDefinition -> // Subprogram definition ( subpDefCode attr LocalSymTable_ // SymTable local in the subprogram. SubpNode @ // Subprogram name. InitiationPart_ @ // Subprogram initiation. SubpBody_ @ ) // HIR subprogram body // (Control flow should be ended by return). // LIR @ ) // LIR representation for the subprogram. //##24 deleted SubpNode -> // Subprogram name node. ( symCode attr subpSym ) LocalSymTable_ -> // Local symbol table (for subprogram, block, etc.) SymTable | null SubpBody_ -> // HIR subprogram body is BlockStmt // block statement or | ( labeledStmtCode attr // BlockStmt with Label. LabelDefinitionList_ @ // List of label definitions. BlockStmt @ ) // Statement body BlockStmt -> ( blockCode attr LocalSymTable_ // Define symbols local in the block. StmtSeq_ @ ) // Block makes a sequence of statements // to be treated as one statement. // Statements in StmtSeq_ can be get // by getFirstStmt() and successive getNextStmt(). StmtSeq_ -> Stmt @ StmtSeq_ @ // Statement sequence is a statement | null // followed by statements or null. Stmt -> // Statement is LabeledStmt // a statement with label definitions or | StmtBody_ // a statement without label definition. LabeledStmt -> // Statement with label definition. ( labeledStmtCode attr LabelDefinitionList_ @ // List of label definitions. StmtBody_ @ ) // Statement body (statement that is // peeled label off). LabelDefinitionList_ -> // List of LabelDef nodes. ( listCode attr List_of_LabelDef @ ) LabelDef -> // Label definition node. ( labelDefCode attr labelSym ) StmtBody_ -> // Statement body. AssignStmt // Assignment statement. | IfStmt // If statement. | JumpStmt // Jump (goto) statement. | LoopStmt // Loop statement. | CallStmt_ // Subprogram call statement. | ReturnStmt // Return statement. | SwitchStmt // Switch (case selection) statement. | BlockStmt // Block statement. | ExpStmt // Expression treated as a statement. | SetDataStmt // Set initial data statement. AssignStmt -> // Assign statement. ( assignCode attr Exp_l_ @ // l_value expression Exp @ ) // Expression whose value is to be assigned. | ( CompoundAssignOperator_ attr // HIR-C only Exp_l_ @ Exp @ ) | ( IncrDecrOperator_ attr // HIR-C only Exp_l_ @ ) Exp_l_ -> // l-value expression is Exp // an expression representing an object // (memory area to contain data). IfStmt -> // If statement ( ifCode attr ConditionalExp_ @ // Conditional expression. ThenPart_ @ // Then-part ElsePart_ @ // Else-part. LabeledNull_ @ ) // End-of-if label. ThenPart -> LabeledStmt // Executed if ConditionalExp is true. | null ElsePart -> LabeledStmt // Executed if ConditionalExp is false. | null LabeledNull_ -> // A labeled statement whose statement ( labeledStmtCode attr // body is null at the first HIR LabelDefinitionList_ @ // generation but it may become StmtBody @ ) // non-null by code optimization, etc. JumpStmt -> ( jumpCode attr // Jump to the statement with LabelNode @ ) // specified label. LoopStmt -> // Loop statement is either for-loop, while-loop, // repeat-loop, indexed loop, or other general loop. // All of them are implemented as a general loop // with some restriction depending on the loop type. // Compiler components (other than front part) should // treat general loop, that is, do not assume some child // is null without checking whether the child is null // or not. // There may be some cases where processing become // simple if the loop is either for-loop, repeat-loop, // etc. ( LoopCode_ attr // Loop kind code. LoopInitPart_ @ // Loop initiation part to be executed // before repetition. This may be null. // LoopInitPart_ should not contain // control statements. //##24 ConditionalInitPart_ @ // Conditional initiation part. // This is deleted. Give null. //##24 StartConditionPart_ @ // Loop start conditional expression // with loopBackLabel. // If true, pass through to LoopBody_, // otherwise transfer to LoopEndPart_. // If loop start condition part is null , // pass through to LoopBody_. LoopBody_ @ // Loop body repetitively executed. // Pass through to EndCondition_. // It is a block statement (BlockStmt) // with loop start label and the blcok // statement contains a labeled statement // with loopStepLabel as its last statement. // This should not be null but the block may // have no executable statement and contains // only a labeled statement with loopStepLabel. // "continue" jumps to the loopStepLabel. // The loopStepLabel may be omitted if // there is no "jump loopStepLabel". EndCondition_ @ // Loop end condition expression. // If true, transfer to LoopEndPart_, // otherwise pass through to // LoopStepPart_. LoopStepPart_ @ // Loop step part executed // before jumping to loopBackLabel. // LoopStepPart_ should not contain // control statements. //##24 LoopEndPart_ @ ) // Loop end part // with loopEndLabel. // "exit" (break in C) jumps to here. IndexedLoop_ attr // Attributes for IndexedLoop. //##21 // Not given for other loops. //##21 LoopCode_ attr -> whileCode attr // while-loop | forCode attr // for-loop | repeatCode attr // repeat-loop | indexedLoopCode attr// indexed-loop //##21 | loopCode attr // general loop other than above loops. //##21 LoopInitPart_ -> // Loop initiation part. Stmt | null ConditionalInitPart_ -> // Executed at first time only. null // This is deleted. Give null. //##24 StartConditionPart_ -> // Show start condition with ( labeledStmtCode attr // loopBacklabel. LabelDefinitionList_ @ ExpStmtOrNull_ @ ) // loopStartConditionExpression. LoopBody_ -> // Block statement with loopBodyLabel. ( labeledStmtCode attr // The last statement of the block LabelDefinitionList_ @ // is a LabeledNull_ statement with BlockStmt_ @ ) // loopStepLabel. EndCondition_ -> // ExpStmt showing loop end condition. ExpStmtOrNull_ LoopStepPart_ -> // Statement to be executed before jumping Stmt // to loopBackLabel. | null LoopEndPart_ -> // LabeledNull_ statement with loopEndLabel. LabeledNull_ NullOrStmt_ -> // Usually null but it may be null // a statement (created during | Stmt // HIR transformation). //##20 ExpStmtOrNull_ -> // Expression statement or null . ExpStmt | null // IndexedLoop_ attr -> // Attributes for IndexedLoop. loopIndex attr // Loop index (induction variable). // See getLoopIndex(). startValue attr // Start value of the loop index. // See getStartValue(). endValue attr // End value of the loop index. // See getEndValue(). stepValue attr // Step value for the loop index. // See getStepValue(). // Note. LoopInf may contain goto-loop that is difficult or // impossible to be represent by above LoopStmt. // (goto-loop is not implemented by LoopStmt.) //##21 // LoopStmt is executed as follows: // LoopInitPart_; // if (loopStartConditionExpression != null) { // if (loopStartConditionExpression == true) { // jump to loopBodyLabel; // }else // jump to loopEndLabel; // }else // jump to loopBodyLabel; // loopBackLabel: // if ((loopStartConditionExpression != null)&& // (loopStartConditionExpression == false)) // jump to loopEndLabel; // loopBodyLabel: // Start of BlockStmt of LoopBody_ // Stastement sequence of the BlockStmt; // loopStepLabel:; // End of BlockStmt of LoopBody_ // if ((loopEndConditionExpression != null)&& // (loopEndConditionExpression == false)) // jump to loopEndLabel; // LoopStepPart; // jump to loopBackLabel; // loopEndLabel: // Loop end part; // BEGIN #21 // ForStmt is created as a general loop where contents of // ConditionalInitPart_, EndCondition_, LoopEndPart_ // are labeled null at first (but their statement body may // become not null by some optimizing transformation). // See isSimpleForLoop(). // WhileStmt is created as a general loop where contents of // LoopInitPart_, ConditionalInitPart_, EndCondition_, // LoopStepPart_, LoopEndPart_ // are labeled null at first (but their statement body may // become not null by some optimizing transformation). // See isSimpleWhileLoop(). // RepeatStmt is created as a general loop where contents of // LoopInitPart, ConditionalInitPart_, StartCondition_, // LoopStepPart_, LoopEndPart_ // are labeled null at first (but their statement body may // become not null by some optimizing transformation). // See isSimpleRepeatLoop(). // IndexedLoopStmt is created as a general loop where contents of // ConditionalInitPart_, EndCondition_, LoopEndPart_ // are labeled null at first (but their statement body may // become not null by some optimizing transformation). // See isSimpleIndexedLoop(). // IndexedLoopStmt represents a Fortran type loop where // value of loop index is incremented or decremented by loop // step value starting from loop start value and stops // to loop before crossing the barrier of loop end value. // (See IndexedLoopStmt interface.) // Indexed loop attributes (IndexedLoopAttr_) are available // only for IndexedLoopStmt. // END #21 CallStmt_ -> // Subprogram call statement. ( expStmtCode attr // Expression statement FunctionExp @ ) // with FunctionExp. FunctionExp -> // Subprogram call expression. ( callCode attr Exp @ // Expression specifying // subprogram to be called. HirList_ @ ) // Actual parameter list. //##24 ReturnStmt -> // Return statement. ( returnCode attr ReturnValue_ @ ) // Return value. ReturnValue_ -> Exp | null SwitchStmt -> // Switch statement. ( switchCode attr Exp @ // Case selection expression. JumpTable_ @ // List of constants and statement labels. Stmt @ // Collection of statements to be selected. LabeledNull_ @ ) // Indicate end of case statement. JumpTable_ -> // Jump table. ( seqCode attr JumpList_ @ // List of constant-label pairs. LabelNode @ ) // Default label. JumpList_ -> // Jump list. ( listCode attr // Correlate Exp value List_of_SwitchCase @ ) // and list of SwitchCase_ pairs. SwitchCase_ -> // List of SwitchCase_ pairs. ( seqCode attr ConstNode @ // Correlate Exp value and LabelNode @ ) // switch statement label. ExpStmt -> // Expression statement. ( expStmtCode attr Exp @ ) // Expression treated as a Stmt. NullNode -> ( nullCode attr ) // NullNode is a terminal ; // that is not null. InfStmt -> //##24 ( infCode attr // Information node (terminal). InfKind_ // Information kind identifier. InfObject_ ) // Information. // (InfKind_ and InfObject_ are not // traversed by HIR traverse operations.) InfKind_ -> stringConst // String constant showing the kind of ; // information such as pragma, comment, etc. InfObject_ -> // Information. Object // Object such as Sym, Exp, etc. or // a list of Objects. It may or may not be HIR. ConditionalExp_ -> // boolean expression Exp Exp -> //Expression. Factor_ | UnaryExp_ | BinaryExp_ | ExpListExp //##24 | SelectExp // HIR-C only | NullNode //##24 | InfNode Factor_ -> ConstNode | SymNode | CompoundVar_ | FunctionExp | PhiExp //| AssignStmt // HIR-C | ExpListExp //##24 | HirSeq // Sequence of objects UnaryExp_ -> // Unary expression. ( UnaryOperator_ attr Exp @ ) | ( sizeofCode attr　 // size of the type of Exp Exp @ ) 　　　　 | ( sizeofCode attr // size of the type TypeNode @ ) // represented by TypeNode. BinaryExp_ -> // Binary expression. ( BinaryOperator_ attr Exp @ Exp @ ) CompoundVar_ -> // Compound variable. SubscriptedExp // Subscripted variable. | PointedExp // Pointed variable. | QualifiedExp // Qualified variable. SubscriptedExp -> Subscripted variable. //##14 ( subsCode attr // Array with subscript expression. Exp @ // Expression indicating the array. Exp @ ) // Subscript expression. //##24 | ( subsCode attr //##24 Exp @ // Expression indicating an array. //##24 ExpList @ ) // List of Subscripts. //##24 ; // (1st subscript, 2nd subscript, //##24 // etc. for rectangular array.) ElemSize_ -> // Element size. Exp QualifiedExp -> // Qualified expression. ( qualCode attr // Qualified variable Exp @ // Should represent a structure or union. ElemNode @ ) // struct/union element. // | ( qualCode attr // Class field // Exp @ // Should represent a class. // FieldNode @ ) // Field of the class. PointedExp -> // Pointed expression. ( arrowCode attr // Pointed variable Exp @ // Expression representing a variable PointedElem_ @ ) // Pointed element. PointedElem_ -> ElemNode // Pointed element (with displacement). | null // Pointed location (0 displacement). ConstNode -> ; // Constant symbol. ( constCode attr intConst ) // integer constant | ( constCode attr floatConst ) // float constant | ( constCode attr charConst ) // character constant | ( constCode attr stringConst ) // string constant | ( constCode attr boolConst ) // boolean constant SymNode -> // Symbol node. (symCode Sym ) // Program name, etc. | VarNode | SubpNode | LabelNode | ElemNode //##16 not DELETED | TypeNode VarNode -> ( symCode attr varSym ) // Variable name node SubpNode -> ( symCode attr subpSym ) // Subprogram name node LabelNode -> ( symCode attr labelSym ) // Label reference node ElemNode -> ( symCode attr elemSym ) // structure/union element ; ; // name node. // FieldNode -> ( symCode attr fieldSym ) // Field name node. TypeNode -> ( symCode attr typeSym ) // Type name node FunctionExp -> // Function expression. ( callCode attr Exp @ // Expression specifying function // to be called (SubpNode, etc.). HirList_ @ ) // Actual parameter list. // It is HirList whose elements are Exp. IrList -> ( listCode attr // A List that can be treated as IR. List_of_Objects_ @ ) HirList -> ( listCode attr // An IrList that can be treated as HIR. List_of_Objects_ @ ) ExpListExp -> // Expression representing //##24 ( expListCode attr // a list of List_of_Exp @ ) // expressions in HIR form. HirSeq -> ( seqCode attr HIR @ ) // Sequence of some definite | ( seqCode HIR @ HIR @ ) // number of HIR nodes. | ( seqCode HIR @ HIR @ HIR @ ) | ( seqCode HIR @ HIR @ HIR @ HIR @ ) PhiExp -> (phiCode attr FlowVarList_ @ ) // phi function FlowVarList_ -> ( listCode attr List_of_VarLabelPair @ ) // List of (Var Label) pairs. VarLabelPair -> ( listCode attr VarNode @ Label @) //##9 UnaryOperator_ -> notCode // bitwise not (~) one's complement //logical not (boolean not) (!) | negCode // negate (unary minus) | addrCode // get address (&) | contentsCode // get contents of pointed memory | convCode // type conversion for basic type | decayCode // convert array to pointer | castCode // type conversion by cast for pointer | sizeofCode // sizeof operator | encloseCode // honor parenthesis | IncrDecrOperator_ // Increment/decrement. HIR-C only. BinaryOperator_ -> | addCode // add (+) | subCode // subtract (-) | offsetCode // Offset between pointers (HIR-C only) | multCode // multiply (*) | divCode // divide (/) | modCode // modulo (%) | andCode // bitwise and, boolean and (&) | orCode // bitwise or, boolean or (|) | xorCode // bitwise exclusive or, boolean exclusive or (^) | shiftLLCode // shift left logical (<<) // | shiftRCode // shift right arithmetic (>>) | shiftRLCode // shift right logical (>>) // | undecayCode // convert pointer to array //##10 | expRepeatCode // Repeat constant values (operand 1) // count (operand 2) times. | CompareOperator_ | CompareZeroOperator_ // HIR-C only //##20 | ShortCircuitOperator_ // HIR-C only | commaCode // comma operator // HIR-C only CompareOperator_ -> cmpEqCode // equal | cmpNeCode // not equal | cmpGtCode // greater than | cmpGeCode // greater or equal | cmpLtCode // less than | cmpLeCode // less or equal CompareZeroOperator_ -> // HIR-C only //##20 eqZeroCode // equal zero // HIR-C only //##20 ShortCircuitOperator_ -> // HIR-C only lgAndCode // logical and (&&) // HIR-C only | lgOrCode // logical or (||) // HIR-C only IncrDeclOperator_ -> ; ; // HIR-C only preIncrCode // pre-increment (++) // HIR-C only | preDecrCode // pre-decrement (--) // HIR-C only | postIncrCode // post-increment (++) // HIR-C only | postDecrCode // post-decrement (--) // HIR-C only CompoundAssignmentOperator_ -> // HIR-C only multAssignCode // *= // HIR-C only | divAssignCode // /= // HIR-C only | modAssignCode // %= // HIR-C only | addAssignCode // += // HIR-C only | subAssignCode // -= // HIR-C only | shiftLAssignCode // <<= // HIR-C only | shiftRAssignCode // >>= // HIR-C only | andAssignCode // &= // HIR-C only | xorAssignCode // ^= // HIR-C only | orAssignCode // |= // HIR-C only SelectExp -> // (Exp ? Exp : Exp) // HIR-C only ( selectCode attr ConditionalExp @ Exp @ Exp @ ) attr -> // Attribute attached to the HIR node //##20 typeSym // Shows the type of HIR subtree. OptionalAttrSeq_ // Sequence of optional attributes // that are not inevitable at the first stage // of HIR generation. The optional attributes // may be attached to give information used // in some specific compiler modules or // to help compiling processes. OptionalAttrSeq_ -> OptionalAttr_ OptionalAttrSeq_ | null OptionalAttr_ -> StmtAttr_ // Attributes for statements | IndexNumber_ // Index number to identify the HIR node. | Flag_ // true/false flag. | InfItem_ // Node-wise information. | ExpId // Expression identifier used in flow analysis. | Work_ // Phase-wise information. StmtAttr_ -> // Attributes attached to statement subtrees. FileName_ // Source program file containing the statement. LineNumber_ // Line number of the line in which the // statement started. FileName_ -> stringConstValue LineNumber_ intConstvalue IndexNumber_ -> intConstValue Flag_ -> FlagNumber_ FlagValue_ FlagNumber_ -> intConstValue // Such as FLAG_NOCHANGE, FLAG_C_PTR, // FLAG_CONST_EXP FlagValue_ -> true | false InfItem_ -> InfKind_ InfObject_ ---------- 削除した項目 　ループのConditionalInitPart ##24 UntilLoop (replaced by RepeatLoop) //##47 　添字のindex表現　##24