2003/6/14 　Ｖ．　フロー情報の概要 　　　　　　　　　　　　　　　　　　(##21: 2003/06 改訂) 　　　　　　　　　　　　　　　　　　(##14: 2002/06 改訂) 　　　　　　　　　　　　　　　　　　(##10: 2001/11 改訂) 　　　　　　　　　　　　　　　　　　(##9 : 2001/10 改訂） １．　フロー情報の構成 （１）フロー情報のまとめかた　(##9) 　並列化や最適化においては、プログラムを基本ブロックに分割し、それをも とに制御の流れを解析するための制御フロー情報や、データの流れを解析する データフロー情報を求め、その情報に基づいてプログラム変換を行なうことが 多い。そこで、並列化や最適化の基礎となる制御フロー情報やデータフロー情 報の多くは、基本ブロックに付加する。プログラムにおいて処理時間を多く消 費するのは、反復実行されるループ部分なので、それに対しては特別の配慮が なされる。ループに対する並列化、最適化の情報はループ情報としてまとめる。 この仕様書では、制御フロー情報とデータフロー情報を合わせてフロー情報と 呼び、制御フロー解析とデータフロー解析を合わせてフロー解析と呼ぶ(##10)。 　階層的な並列化のためには、ループや幾つかの基本ブロックをひとまとめに して扱うことも要求されるが、その仕様については、並列化の方式がもう少し 具体化してから設定する。 　基本ブロックの情報はJavaのインタフェースBBlockを介してアクセスし、 ループ情報もJavaのインタフェースLoopInfを介してアクセスする。 　制御フロー情報の主体は、基本ブロックをノード（節）とし、それらを先行、 後続関係で接続した制御フローグラフ（CFG, control flow graph）で表す。 この制御フロー解析の仕様では、単にノードと言えば基本ブロックを表すもの とし、それ以外のものを表すときは、HIRノードなどというように、その旨こ とわる。CFGは副プログラムごとに作られる。副プログラムが複数の入口を持 つ場合は、仮想的な入口基本ブロックを設け、副プログラムの実際の入口に対 応する基本ブロックはその仮想的入口基本ブロックを先行ブロックとすること により、CFGの入口基本ブロックは１つにする。副プログラムが複数の出口を 持つ場合は、仮想的な出口基本ブロックを設け、副プログラムの実際の出口に 対応する基本ブロックはその仮想的出口基本ブロックを後続ブロックとするこ とにより、CFGの出口基本ブロックは１つにする。 　データフロー情報には、基本ブロック内の局所的データフロー情報と、基本 ブロック間の大域的データフロー情報がある。局所的データフロー情報は特定 の処理モジュールの中に限定する形で使われることが多いので、その表現は個 別に定めることにし、この仕様書では、副プログラムごとに作られる大域的デ ータフロー情報について述べる。データフロー情報は、主として、個々の基本 ブロックの入口、出口でデータがどのような状態にあるかを示す形で表現する。 データフロー情報を求めるにはまず制御フローグラフを作る必要がある。 　副プログラムのフロー情報は、JavaのインタフェースSubpFlowを介してア クセスする。１つの副プログラムに対する最適化や並列化の処理を行なうとき は、このSubpFlowからその副プログラムに対する制御フロー情報やデータフ ロー情報へのパスを求め、個々のデータにアクセスする。フロー情報全体を統 括するインタフェースとしてFlowというものがある。 　コンパイラのプログラム構成としては、インタフェースと実現部分が分離し てあり、次のような対応関係がある。 　　インタフェース　　実現部 　　　Flow 　　　　FlowImpl 　　　Subp 　　　　SubpImpl 　　　BBlock 　　　　BBlockImpl 　　　LoopInf　　　　LoopInfImpl 　　　xxx 　　　　xxxImpl 　それぞれの副プログラムのフロー情報は、制御フローについては制御フロー グラフ（CFG）からアクセスしてゆき、データフローについては、CFGのノー ドである基本ブロックごとにアクセスするものが多い。設定・参照情報のよう に、記号表からアクセスできるものもある。 　副プログラム間のフロー情報の仕様については、副プログラム間解析の方式 が少し具体化してから定める。 　別名情報についても、別名解析の方式が少し具体化してから仕様を定める。 　フロー情報の表現形式にはHIRとLIRで共通する部分が多い。データフロー 関連のインタフェースには、後述のように、HIRとLIRで共通にしてあるもの が多い。 （２）フロー情報と他の情報との関連 (##10) 　制御フロー情報は制御フロー解析モジュールで算出し、データフロー情報は データフロー解析モジュールで算出する。並列化や最適化のためにどのような 変換を行えばよいかは、これらの制御フロー情報やデータフロー情報だけを見 て判断できるものもあるが、HIRやLIRを走査しながら変換することや、記号 を見てそれに関連するデータフロー情報を見ることも多い。そこで、HIRでは、 基本ブロックの区切りやループの契機となるHIRノードにデータフロー情報へ のリンクを付加し、HIRを走査しているときにデータフロー情報を参照可能と する。LIRは基本ブロックをノードとする制御フローグラフそのものをLIRの 内部表現としており、その基本ブロックはLIRの部分木の単なるリストという 構造をとるので、制御フローを改めて算出する必要はない(##21)。 　また、記号表の副プログラムには、その入口基本ブロックを示す形でCFGへ のリンクが設定してあり、ラベルに対してはそれに対応する基本ブロックへの リンクがあり、変数など対しては、データの設定・参照リストなどの情報への リンクがある。逆に、基本ブロックからは、その先頭の命令に対応するHIRノ ードやLIRノードへのリンクがある。このようにして、CFGを見ながらデータ フロー情報を参照することや、基本ブロックや制御フロー情報を見ながら対応 するHIRやLIRを参照することができるようになっている。（フロー解析で対 象とするHIRはHIR-CではなくHIR-baseであり、この仕様書でHIRと言うの はHIR-baseのことである。） (##9) 　　HIR　　　←→　　ーーーーーーーーーーーーーーー 　　　↑　　　　　　｜　　　　　　　　　　　　　　　｜ 　　　↓　　　　　　｜　　　　　　制御フロー情報　　｜ 　　記号表　　←→　｜フロー情報　　　↓　　　　　　｜ 　　　↑　　　　　　｜　　　　　　データフロー情報　｜ 　　　↓　　　　　　｜　　　　　　　　　　　　　　　｜ 　　LIR　　　←→　　ーーーーーーーーーーーーーーー 　CFGは基本ブロックをノードとし、先行、後続関係を辺とするグラフであり、 データフロー情報の多くは基本ブロックに付加された情報なので、CFGを見な がらデータフロー情報を参照することができる。　(##9) （３）フロー解析の前段での事前変換　(##10) 　HIRの制御フロー解析を行なうには、まず、副プログラムを基本ブロックに 分割する必要がある。HIRにおける基本ブロックの始まりは、ラベル定義ノー ドで示される。HIRでは、ifのthen部やelse部の先頭、ループの戻り点など、 制御の分岐点と合流点には、コンパイラで生成した内部ラベルがつけられるの で、基本ブロックの終わりは、木構造を深さ優先で左から右への順序で走査す るときに次のラベル定義ノードに出会う直前、または１つの副プログラムの終 わりによって区切られる（４．１節参照）。したがって、副プログラムをHIR の基本ブロックに分割することは、そのような特性を手がかりに基本ブロック の区切りを見分け、制御フロー情報へのリンクをつけることに相当する。具体 的には、HIRでは基本ブロックの先頭となるHIRノードに対して基本ブロック のインスタンスへのリンクを作る。HIRに対して制御フロー解析を行わない場 合は基本ブロックへの分割は行わない。 　LIRは、すでに述べたように、基本ブロックをノードとする制御フローグラ フそのものとして表現されており、その基本ブロックには、L式のリストが直 接含まれている。したがって、LIRは改めて基本ブロックに分割する必要がな い(##21）。 　HIRでもLIRでも、callは基本ブロックの切れ目として扱わない。 　データフロー解析を行なうには、制御フローグラフを作成し、求めようとす るデータフロー情報に合わせて、各基本ブロックにその入れ場所を用意する。 (##9) 　ループに対する並列化や最適化の処理は、完全な入れ子構造を持つループを 対象とすることが多い。そうでないループは、可能ならばそのようなループに 変換しておくことが望ましい(##9)。 （４）フロー情報の更新　 　本コンパイラでは、ソースプログラムをHIRを経由してLIRに変換したのち、 コード生成を行なう。LIRからHIRに逆変換することは想定していない。LIR に変換したとき、HIRをもとに算出した制御フロー情報とデータフロー情報は 無効とし、必要な情報はLIR用に算出しなおす。ただし、ループ情報や並列化 情報の一部は、HIRで算出したものをLIRでも利用することがある。 (##9) 　「共通中間表現仕様の概要」で述べたように、データフロー解析は、並列化 や最適化のために大きいプログラム変換を行なったあとでは再計算する。プロ グラム変換の過程でデータフロー情報を逐一更新する形態はとらないが、１つ の変換モジュールの中でその変換に使うデータフロー情報を更新する必要があ れば、それはその変換モジュールの中で更新する。 　フロー情報の計算は選択的に行ない、常に全情報を更新するわけではない。 何のフロー計算を行なうかは、並列化や最適化で何を要求するかで異なる。フ ロー情報の計算には順序関係もあり、情報 y が情報 x に基づいて計算され、 x が変わると y も変わるならば、y は x に従属するという。ある情報を再計 算した場合は、それに従属する情報も再計算する必要があり、もとの従属情報 を無効にする必要がある。このような情報の従属関係は、自動的に判定できる ものもあるが、一般には、個別のフロー解析ないしプログラム変換のモジュー ル作成時に対処するものとする。 　情報 z が x に基づいて計算はされるが、プログラム変換の内容が x には 影響しても z に影響するまでには至らないものであれば、z を計算しなおす 必要はない。このような場合、z はそのプログラム変換で不変であるという。 どのプログラムで何の情報は再計算し、何は元の情報を利用するかは、個別の プログラム変換のモジュールの作成時、ないしコンパイラの制御プログラムで 対処するものとする。 　アクセスメソッドとしては、情報を選択的に無効化するものを設ける。無効 化された情報を更新して利用するには、それを再計算する必要がある。上記の ことを勘案してコンパイラを構成することにより、HIRで解析して得た並列化 情報や最適化情報をLIRへ伝えること、さらにコード生成部まで伝えることも 可能である。 ２．　基本ブロック 　１つの副プログラム内の基本ブロックの集まりは、先行（predecessor）、後 続（successor）関係を辺（edge）として結合することによって、１つのグラ フを構成する。 これを基本ブロック単位の制御フローグラフ（CFG）という。制御フロー情報 としては、次のようなものを求める。どれを算出するかはオプションであるが、 HIRのフロー解析にあたっては、基本ブロックへの分割とその先行、後続関係 は必ず算出する。 　　　先行、後続関係 　　　支配木 　　　逆支配木 　　　当基本ブロックを含む最内ループ情報へのリンク 　　　ループヘッダ（ループの先頭基本ブロック）か否か 　　　ループの帰辺の出る基本ブロックか否か 　　　ループからの脱出辺の出る基本ブロックか否か 　　　ループプリヘッダ（ループの入口基本ブロック）か否か 　基本ブロックに記録する可能性のある情報としては、後述のデータフロー情 報以外に、 　　　実行頻度 　　　後続ブロックへの辺の相対的分岐確率 　　　演算子の数 　　　ロード命令の数 　　　予想実行時間 などがある。これらは常時計算されているのではなく、並列化や最適化のモジ ュール、あるいはその準備モジュールで選択的に算出され、情報として付加さ れるものであり、フロー解析を行なうとこれらがすべて求まっているというわ けではない。 　支配木の情報としては、各々の基本ブロックに対して、それを直接に支配す る基本ブロック、すなわち支配木における親が示されている。また、それぞれ の基本ブロックに対して、それが直接に支配する基本ブロックのリストを得る メソッドが用意されている。これによって支配木の情報を得ることができる。 逆支配木についても、同様に、各基本ブロックに対して、それを直接に逆支配 する基本ブロックと、それが直接に逆支配する基本ブロックのリスト、すなわ ち支配木における子のリスト、を得るメソッドが用意されている。　(##9) 　基本ブロックに対するデータフロー情報としては、次のようなものを求める。 これらもすべてが常時求められているのではなく、データフロー解析の制御モ ジュールまたはデータフロー解析指示パラメータにより、選択的に求められる ものである。ここで、p はプログラム点、すなわちHIRやLIRにおいて文や式 などを表す部分木の根を表し、p(def(x)) は変数等を表す記号 x を定義する （値を設定する）部分木を表す。 Def(B) = { p | for some x, p(def(x)) is included in B and after that point there is no def(x) in B. } Kill(B) = { p | for some x, p(def(x)) is included in B' (where, B' != B) and there exists some definition point of x p'(def(x)) in B. } Reach(B)= { p | there is some path from program point p defining x (that is p(def(x))) to the entry of B such that there is no p'(def(x)) on that path. } Reach(B) = or_all( (Def(B') | (Reach(B') - Kill(B'))) for all predecessors B' of B) Defined(B) = { x | x is set in B. } Exposed(B) = { x | x is used in B and x is not set in B before x is used. } EGen(B) = { op(x,y) | expression op(x,y) is computed in B and after that point, neither x nor y are set in B. } Thus, the result of op(x,y) is available after B. EKill(B) = { op(x,y) | operand x or y is defined in B and the expression op(x,y) is not re-evaluated after that definition in B. } If t = op(x,y) is killed in B, then op(t,u) should also be killed in B. AvailIn(B) = { op(x,y) | op(x,y) is computed in every paths to B and x, y are not set after the computations on the paths. } Thus, the result of op(x,y) can be used without re-evaluation in B. AvailOut(B) = { op(x,y) | op(x,y) is computed in every path to the exit of B and x, y are not set after the computations on the paths. } Following relations hold. AvailIn(B) = and_all(AvailOut(B') for all predecessors B' of B) if B is not an entry block; AvailIn(B) = { } if B is an entry block. AvailOut(B) = EGen(B) | (AvailIn(B) - EKill(B)) LiveIn(B) = { x | x is alive at entry to B, that is, on some path from entrance point of B to use point of x, x is not set. } LiveOut(B) = { x | x is live at exit from B, that is, there is some path from B to B' where x is in Exposed(B'). } Following relations hold. LiveOut(B) = or_all(LiveIn(B') for all successors B' of B) LiveIn(B) = Exposed(B) | (LiveOut(B) - Defined(B)) DefIn(B) = { x | x is always defined at entry to B whichever path may be taken. } DefIn(B) = and_all(DefOut(B') for all predecessors B' of B) DefOut(B) = { x | x is always defined at exit from B whichever path may be taken.} DefOut(B) = Defined(B) | DefIn(B) 依存関係情報　　　 　　　フロー依存 　　　逆依存 　　　出力依存 　　　入力依存 フェーズ別情報 　　最適化や並列化のそれぞれのフェーズで個別に利用する情報を 　　保持できるように、その入れ場所が用意されている（getWork(), setWork()）。 　　それはJavaのObjectクラスとしてあるので、内容は任意に設定できる。 フラグ 　　フラグ番号（1 ~ 31） を指定して、それに対応する情報のtrue/falseを 　　記録できる（getFlag(), setFlag()）。個々のフラグ番号が何を表すかは 　　ある規約のもとに自由に設定できる（FlagBoxインタフェース参照）。 ３．　ループ情報 　ループには、for-loop, while-loop, repeat-until-loop、gotoによるルー プ、ならびに、ループ指標変数とその始値、終値、増分値を指定する IndexedLoop（FortranのDOループ）がある。それらはHIR上でもLoopクラ スのサブクラスとして構成されるが、フロー情報としても、階層をもったルー プ情報クラスとして構成される。forループかwhileループかなどを区別する 必要のない処理はLoopInfの情報とそのメソッドを利用して行う。 LoopInf |-- ForLoopInf | |-- DoAllLoopInf |-- WhileLoopInf |-- UntilLoopInf |-- IndexedLoopInf　(##9) |-- GotoLoopInf　(##10) 　ループに対して記載する主な情報は次のようなものを予定しているが、詳し くはループ解析情報の仕様書を参照されたい(##9)。 　　親ループ 　　入れ子ループリスト 　　帰納変数リスト 　　入口基本ブロック 　　開始時判定式 　　終了時判定式 　　ループ本体を構成する基本ブロックのリスト　 　　継続（continue）先基本ブロック 　　次ステップ準備基本ブロック（帰納変数増減等の処理を行なう基本ブロッ ク） 　　ループラベル（開始点、途中脱出先、継続先、終了点） 　　等価なリダクション関数（総和、最大値、最小値等） 　　一時配列リスト 　　各種フラグ 　　　　並列化可否 　　　　可能な並列化の種別 　　　　callの包含の有無 　　　　gotoによる飛び出しの有無 　　　　不確定設定（ポイント先、構造体要素、他への設定）の有無 ４．　基本ブロックにおける処理内容の表現　　 ４．１　HIRに対する基本ブロック　 （１）HIRと基本ブロック 　HIRでは、１つの選択文や反復文は複数の基本ブロックにまたがる。１つの 基本ブロックは、複数の文を含むことがあり、分岐を含まない文（単純文）の 列として構成されることがある。１つの基本ブロックは、代入文や比較式とそ れに続く分岐命令で構成されることもある。従って、HIRの構成単位と基本ブ ロックの区切りは、単純な包含関係では表せない。先に述べたように、基本ブ ロックの先頭にはラベルがついており、その後ろでは１つの式または文が始ま る。基本ブロックの区切りは、if文などの１つの文が完結する以前に来るこ ともあり、幾つかの文が続いたあとに来ることもある。 　HIRにおける基本ブロックの開始点は具体的には次のようになる。空と付記 してあるのは空の基本ブロックが作られる場合があることを示している。 　　　副プログラムの先頭 　　　ifのthen部の先頭（then部がないと空の基本ブロックが作られること がある） 　　　ifのelse部の先頭（else部がないと空の基本ブロックが作られること がある） 　　　ifの終了点 　　　ソースラベル定義（ラベル定義が連続しているときはそれらを合わせて 　　　　　　　　　　　　１つ基本ブロックにまとめる） 　　　forのループ開始判定点、ループ本体の先頭、終了判定点、 　　　　　ループステップ点、ループ終了点 　　　whileのループ開始判定点、ループ本体の先頭、終了判定点（空）、 　　　　　ループステップ点（空）、ループ終了点 　　　untilのループ開始判定点（空）、ループ本体の先頭、終了判定点、 　　　　　ループステップ点（空）、ループ終了点 　　　switchの各選択肢の先頭とswitch終了点 　　　jumpの直後 　　　returnの直後 ifの条件部やforの初期設定部は直前の基本ブロックの延長として扱われ、 ifやfor, while, until等の制御文の直後にあるラベルなしの文は、これら の制御文の終了点で始まる基本ブロックの延長として扱われる。　(##10) 　HIRでは、基本ブロックの区切り方はあまり単純でないので、基本ブロック の中の命令を走査するには、次の小項目に示すように、それ用に準備されたイ テレータを使う(##9)。それらのイテレータは、式や文の区切りにとらわれず に、１つの基本ブロックに含まれる式や文、あるいはそれらの一部分を順次走 査する(##10)。 　基本ブロックは、単なる式または文の列と見ることもできるが、HIRの部分 木の一部分と見ることもできる。実体にのみ着目する前者の見方では、制御フ ローは基本ブロックのグラフで表現されているとして、制御フローを規定する ifやwhile等のHIRノード、あるいは文をまとめるブロックノードは見えず、 そこに含まれる式や代入文、関数呼出などが実行される順番に合わせて順次取 り出されるとする。基本ブロックを部分木の一部として扱う後者の見方では、 その基本ブロックに含まれる（次の基本ブロック開始点の直前までの）HIRノ ードを、ifやwhile、ブロック等も含めて、全部見ることができる。この見方 の違いは、使うイテレータが何であるかによって区別される。 （２）基本ブロック内の実体にのみ着目する場合 　基本ブロック内の実体にのみ着目するときは、構造を表わすだけで実質的演 算を表わさないノードはスキップし、式、または文本体を表す部分木（top- subtree）のみを実行順序にしたがって順次アクセスすることができる。if文 は条件節を含む基本ブロックと、then部を表す基本ブロック群、else部を表 す基本ブロック群に分解される。条件節を含む基本ブロックの実体を取り出す と、ifノードではなく、条件節の部分木が取り出される。then部（の一部） を含む基本ブロックの実体を取り出すと、then部が単純文であるとその文本 体が取り出され、then部がブロック文であればブロックの中の文の文本体が 取り出される。while文は条件節を含む基本ブロックと、ループ本体を表す基 本ブロック群に分解される。ループ本体（の一部）を表す基本ブロックの実体 を取り出すと、ループ本体が単純文であればその文本体が取り出され、ループ 本体がブロックであればブロックの中の文の文本体が取り出される。このよう に、基本ブロックが分岐を含まない式で構成されるときはその式が取り出され、 分岐を含まない文（単純文）の列で構成されるときはその単純文の文本体が 次々と取り出される。 　具体的には、BBlockSubtreeIteratorというイテレータが用意してあり、基 本ブロックBに対して、 　　　BBlockSubtreeIterator subtreeIterator; 　　　HIR currentSubtree; 　　　subtreeIterator = B.bblockSubtreeIterator(); 　　　currentSubtree = subtreeIterator.next(); と指定すると、Bの中の最初の式または文を表す部分木がcurrentSubtreeと して取り出される。そのとき、基本ブロックの先頭についている labeledStmtNodeはスキップされて、subtreeIteratorはその下にある文本体 に位置づけられる。（ただし、文本体を持たないlabeledStmtNodeの場合は labeledStmtNode自体に位置付けられる。）位置づけられようとする先が blockNodeであると、さらにそのブロックの中の最初の文を表す部分木に位置 づけられ、それがnext()によって取り出される。 　以後、 　　　currentSubtree = subtreeIterator.next(); とすると、その次の式または文を表す部分木が次々と取り出される。ここで、 次の式または文というのは、subtreeIteratorの位置づけている式または文を x とすると、まず、x がリストの要素であれば次のリスト要素、x が文であれ ば次の文、x がその他のノードの第 i 子であればそのノードの第 i+1 子のこ とを意味する。位置づけられようとする先がblockNodeであると、さらにその ブロックの中の最初の文に位置づけられる。currentSubtreeがブロックの最 後の文であるときにnext()が呼ばれると、そのブロックの次に位置する式や 文に位置づけられ、取り出される。このようにして、ブロック内の文はあたか もブロックで囲まれていないかのようにたどってゆかれる。subtreeIterator の位置づけ先は現在の基本ブロックの中に限定される。 　　　subtreeIterator.hasNext() は、次があればtrue、なければfalseを返す。次のない時、あるいは次には スキップされるHIRノードしかない時にnext()を呼ぶと、nullが返される。 ラベルが先頭についている文や内部ラベルが先頭についているwhileループや untilループは、必ず基本ブロックの先頭にあるので、２番目以降のnext()で 位置づけられることはない。 　Cのソースプログラムで l1: l2: a = 1; のようにかかれていても、ラベルl1, l2 の定義はともに文 a = 1; のラベル 定義リストの中に含まれるので、最初のnext()で a = 1; が出てきて、２番 目以降のnext()で位置づけられることはない。ただし、Stmtインタフェース で用意されているメソッド attachLabel(label) を使わないでラベルを文に付加したり、ラベル定義文を単独に作った場合には、 １つの文の前に複数のラベルが定義されることがあり、その場合は空の基本ブ ロックが幾つか作られる。したがって、Stmtインタフェース等にそなえつけ てあるメソッドを使わないでHIRを生成したり変更したりすることは、他のメ ソッドがうまく機能しなくなることがあるので、好ましくない。　(##10) 　BBlockSubtreeIterator には、next()の他に nextStmt() というメソッドが あり、これを使うと、HIRの文としての部分木のみが順次出てくる。基本ブロ ックには、ifやwhileの条件式、プラグマなどの情報を表すInfノードなど がtop-subtreeとして含まれるが、それらはnextStmt()ではスキップされる。　 (##9) 　文の単位ではなくノード単位で走査するときは、次項に述べる BBlockNodeIteratorのnextExecutableNode()というメソッドを使うと、実質 演算を伴わないノードと基本ブロックの接続を表わすjumpノードはスキップ し、実行可能な演算を表わすノードのみを順次アクセスすることができる。 （３）基本ブロックを部分木の一部と見る場合 　基本ブロックの内容をHIRを構成する部分木の一部として見る場合、それを 構成するノードを順次走査する。その順序はHIRを走査した場合と同じである。 走査のメソッドとしては、すべてのノードを走査するものと、実質演算を表わ すノードのみを走査するものがある。具体的には、BBlockNodeIteratorとい うiteratorが用意してあり、基本ブロックBに対して、 　　　BBlockNodeIterator nodeIterator; 　　　HIR currentNode; 　　　nodeIterator = B.bblockNodeIterator(); 　　　currentNode = nodeIterator.next(); と指定すると、Bの先頭部にあるlabeledStmtNodeはスキップされるが、その 後ろにある式や文にcurrentNodeが位置づけられる。 　以後、 　　　currentNode = nodeIterator.next(); とすると、Bの中のHIRの部分木に対して、それを深さ優先で左から右へ走査 するときの順番にしたがって、HIRノードを順次取り出す(##9)。位置づけ先 は現在の基本ブロックの中に限定される。 　　　nodeIterator.hasNext() は、次があればtrue、なければfalseを返す。次のない時にnext()を呼ぶと nullが返される。next()では、構造を指定するためのblockNodeやlistNode、 ifNode、forNode、switchNodeなども出てくる。 　BBlockNodeIteratorのもう１つのメソッドnextExecutableNode()では、実 質的な演算を行なうノードのみが出てくる。すなわち、 progNode, subpDefNode, labelDefNode, infNode, subpNode, typeNode, labelNode, blockNode, listNode, seqNode, encloseNode, labeledStmtNode, ifNode, forNode, whileNode, untilNode, indexedLoopNode, jumpNode, switchNode, blockNode, expStmtNode, nullNode はスキップされる。 ４．２　LIRに対する基本ブロック　(##14) 　LIRは、すでに述べたように、基本ブロックをノードとする制御フローグラ フそのものとして表現されており、その基本ブロックの内容は、LIRの命令を 表す部分木の単なるリストとなっている(##21)。その走査や組換えの仕方は、 それを利用するプログラムに任されている。 ４．３　フロー解析における情報表現　(##9) 　フロー解析のとき、論理演算を行なうことが多いので、多くの情報をビット ベクトルで表す。すなわち、ビットベクトルの各々のビット位置が何を表すの かを定めておき、同じ種類の情報に対する論理演算をビットベクトル間の論理 演算に置き換えることにより、並列に実行する。そのために何種類かの番号付 けを行なう。フロー解析を行わないときはこのような番号付けはなされない。 　ビットベクトルを用いない離散的な表現方法などもあるが、それは最初の版 では用意されていない。(##14) （１）基本ブロック番号 　制御フロー解析で支配木、逆支配木を求めるとき、ビットベクトルで支配関 係を表現する。そのため、各基本ブロックに基本ブロック番号を割り付け、そ れをビットベクトルのビット位置に対応させる。各々の基本ブロックに対して、 それが支配する基本ブロック、支配される基本ブロックをビットベクトルで表 現する。 （２）プログラム点番号（IRノード番号） 　データフロー解析のときも、多くの情報をビットベクトルで表す。そのため、 各々のプログラム点に番号をつける。各々の基本ブロックに対して、到達する 定義などをこのようなビットベクトルによって表現する。現在、HIRに対して は、コンパイラのデバッグ時の便宜も考えて、副プログラムの処理内容を表す 部分木のすべてのHIRノードに番号づけを行なっているが、実際の計算に際し ては、データの設定を行なうHIRノードに対してのみつけた番号を利用してお り、ビットベクトルが不必要に長くならないようにしている。 （３）変数番号 　変数の値の設定・参照は、変数ごとに１つのビット位置を割り付け、各々の 基本ブロックに対して、値を利用可能な変数はどれであるかなどをビットベク トルによって表現する。番号付けする変数は、宣言された変数全部ではなく、 当該副プログラムで実際に値の設定、参照される変数のみを拾い出して対象と する。 （４）式番号 　HIRに対しては、代入文だけをデータフロー解析の対象にするのではなく、 ある基本ブロックで算出された式、無効にされた式、再計算の必要のない式な ども算定する。HIRでは式は木構造で表され、そこでは演算を行なう各々の節 がそれを根とする部分木で表現される１つの式を表す。そこで、演算を行なう 各々の節に式標識（ExpId, expression identifier）をつけ、その式標識につ けた番号で式のビットベクトルにおける位置を表す。この式標識を一時変数と みなすならば、これは木構造中間表現を４つ組中間表現に変換した場合と同じ 形でデータフロー解析ができることを意味する。たとえば、 　　x = a + b * c; という文に対するHIRは (assign (add (mult ) ) ) ) となるが、ここでaddノードにt1、multノードにt2というExpIdを対応させ るならば、 assign / \ x add t1 / \ a mult t2 / \ b c という木構造で表される。この代入文に対するデータフロー解析は、t1, t2 を一時変数とみた t2 := b * c t1 := a + t2 x := t1 という４つ組中間表現に対する解析と同じ形でできる。すなわち、t2はmult で値を設定され、addで参照されるとみなし、t1はaddで値が設定され、 assignで参照されるとみなすことができる。 　このとき、x = a + b * c; の後ろに 　　y = d + b * c; という式があるとすると、b * c の値は改めて計算しなくてよい場合がある。 これを簡単に見分けることができるようにするため、 assign / \ y add t3 / \ d mult t2 / \ b c のように、b * c に前の文の時と同じt2をExpIdとして対応させるならば、 これは t2 := b * c t3 := a + t2 y := t3 という４つ組中間表現に対応することになる。このように表現すると、２つの 代入文の間でt2を算出するときのオペランドの値 b, c に変化がなければ、 後ろの t2 の計算は削除できることがわかる。したがって、同じ式（同じ部分 木）には同じ式標識（ExpId）を対応させ、変数の値の設定・参照関係と ExpIdの値の設定・参照関係を対比させることにより、基本ブロック間での共 通式の削除を変数の再計算削除と同じ処理モジュールで実行できることがわか る。この場合、ExpId番号は変数番号の一種として扱うことができる。 　HIRに対しては、上記のように、同じ部分木には同じExpIdを対応させるこ とにより、式の番号付けをしている。その理由については付録を参照されたい。 　LIRでは、１つの副プログラムは部分木の列として表現され、その部分木の 中の部分木は式を表しているが、その多くは１つの機械命令で表現できるよう な小さい式であり、HIRとは少し事情が異なる。LIRについては部分木の根に のみ番号付けをすればデータフロー解析をすることができる。　(##14) ４．４　HIRとLIRに対するフロー解析モジュールの共用　(##9) 　HIRとLIRはIRのサブクラスであり、HIRノードもLIRノードもIRノード の一種である。両者について、 　　基本ブロックに基本ブロック番号をつける 　　値を設定する部分木の根のIRノードにプログラム点番号をつける 　　変数に変数番号をつける ならば、その後の制御フロー解析、データフロー解析は、HIRとLIRに対して 同一のモジュールで実行できる。基本ブロックの先行・後続関係はHIRでも LIRでも全く同じ形式で表現される。HIRに対しては式番号は変数番号と同格 に扱い、LIRに対しては仮想レジスタにも番号をつけてそれを変数番号と同格 に扱う。LIRで局所変数は(FRAME )と表現され、記憶域割付 が行われるとフレームポインタからのオフセットで表現されたりするが、その ように変換されても元の変数が何であったかを記録しておくならば、変数番号 をつけることは可能である。（上記の番号付けの仕方については、LIRとフロ ー解析部の仕様を固める段階ではっきりさせる。） 　HIRとLIRで個別に処理しなければならないのは 　　基本ブロックへの分割 　　IRノードへの番号付け 　　データの設定・参照位置の算定 　　基本ブロックとIRノードの間のリンクの設定 　　基本ブロック内のIRを走査するイテレータの作成 　　変数や式標識、レジスタへの番号付け などである。共通のモジュールとして実現できるのは 　　基本ブロックを走査するCFGイテレータ 　　支配木、逆支配木、支配辺境等の算出 　　gotoで構成されるループの検出 　　データフロー方程式の求解 　　　（Reach, AvailIn, AvailOut, 他、多数） 　　フロー解析結果の表示 など、フロー解析の主要部をなす部分である。 ５．　フローグラフの変更　　　 ５．１　HIRに対する基本ブロックの内容の変更 　基本ブロックの内容の変更は、式のオペランドの変更、演算子の変更、式の 削除、ならびに、文の追加、挿入、削除、文の構成要素の変更などの形をとる。 先に述べたように、基本ブロック内の文など、トップレベルの部分木（の根の ノード）を走査するにはBBlcokSubtreeIteratorが使える。文の追加、削除は、 これを使って変更や追加、削除する文を位置づけたのち、addNextStmt(HIR x, ) というメソッドを呼ぶと、現在位置づけられている文の次に（次に nextStmt()とやったとしてでてくる文の手前に）文 x を挿入する。 deleteThisStmt()というメソッドを呼ぶと、現在位置づけられている文を削除 する。これによって、文を単位とする追加や削除ができる。　(##21) 　基本ブロックの中のトップレベルの部分木の下位にある構成要素を変更する ときは、BBlockSubtreeIteratorで変更対象とするトップレベルの部分木に位 置づけたのち、HirIteratorを利用して対象とする要素を位置づけ、 replaceThisNode()などのメソッド利用するか、あるいはIRの replaceSource1(IR pSourceOperand), replaceSource2(IR pSourceOperand), replaceSource( int pChildNumber, IR pOperand) replaceResultVar(IR pOperand) などの基本的なメソッドを利用して変更する。このとき、基本ブロックのすべ てのノードを走査するBBlockNodeIteratorを使って変更対象を位置づけ、同 じようにIRのメソッドを利用して変更してもよい。　(##9) 　上記のような基本ブロックの内容の変更は、基本ブロックにリンクされてい るHIRを変更するものである。逆に、CFGから見るのではなく、HIR自体を HirIterator を使って走査し、変更を行ってもよい。変更が基本ブロック内の 処理に限定されている場合は、制御スローグラフは変わらないのでCFGの情報 はそのまま利用できるが、データフロー情報は再計算しないと使えなくなる。　 (##9) ５．２　HIRにおける基本ブロックのグラフ構成の変更 　最適化や並列化で行われるプログラム変換では、基本ブロックの内容変更の みにとどまらず、そのグラフ構成が変更されることがある。それは基本的には、 基本ブロックの挿入、削除、辺の挿入、削除、変更であるが、プログラムとし ての意味を保全するような変換であるため、全く任意の変更というわけではな い。よく行われる変換は 　　　辺の途中への基本ブロックの挿入 　　　ループヘッダの挿入 　　　ループの出口への新たな基本ブロックの挿入 　　　分岐先の変更 　　　複写した部分グラフを挿入 　　　複写した複数の部分グラフを並列に配置 　　　（複写した複数の部分グラフの入口を１つにまとめ、出口を１つに 　　　　まとめることによって束にして接続し、並列実行させる） 　　　空になった基本ブロックの削除 　　　部分グラフを１つの基本ブロックに縮退 などである。 　一般に、ある基本ブロックを挿入するには、そこへの流入辺と流出辺の指定、 もとの辺のつなぎ換えや削除の指定が必要である。たとえば、基本ブロック B1からB2への辺にB3を挿入する場合、B1からB2への辺は、B1からB3への 辺とB3からB2への辺に変換される。また、基本ブロックB1の前にB2を挿入 する場合、B1へ流入する辺はB2へ流入し、B2からB1への辺が構成される。 ある部分グラフを挿入するときは、その部分グラフへ流入する辺とそこから流 出する辺に対して、その接続先を指定する。空になった基本ブロックB1を削 除する時は、B1に流入する辺をB1の流出先に接続する。このような変換だけ でなく、その他の辺のつなぎ換えや削除、挿入が要求されたりする。 　HIRではif-then-elseやループなどの制御構造を有するので、備え付けの 改変メソッドは、そのような構造を崩さない範囲内で実行できる変更に限って 行なう。空の基本ブロックを挿入したとき、当初はHIRの対応部分はnullと するが、そこに式が入ればnullを式に置き換え、文が入ればその文を要素と する基本ブロックで置き換える。基本ブロックに文が追加されれば、HIRのブ ロック文の中に文が追加される。if-then-elseの外郭構造（入口、出口、 then部、else部の接続関係）をこわさない範囲で基本ブロックを変更する場 合は、HIRでも、もとのif-then-elseの構造は保持したまま、その構成部分 の変更を行なう。ループの外郭構造（入口、出口、帰辺、ステップ部の接続関 係）をこわさない範囲で基本ブロックを変更する場合は、HIRでも、もとのル ープ構造を保持したままその内部の構成を変える。（未実装） 　if-then-elseやループなどの元の外郭構造をこわすような変形をHIRに対 して行うよう指示する場合、その指示に先立って、該当するf-then-elseやル ープなどの文をgoto文を使って変換するためのメソッドを呼び出す必要があ る。その変換メソッドによって、変更部分を含むif-then-elseやループを goto文を使って書き直すと、元の構造にとらわれない変更が行えるようにな る。（未実装）　(##9) 　HIRは木構造なので、変更にあたっては、木という構造をこわさないように しなければならない。同じノードや部分木を別のノードに接続すると、枝先が くっつくことになって、木構造でなくなる。基本的には、新規に作るかコピー して作ったノードや部分木を接続するようにしなければならない。コピーする には１つのノードだけコピーするのではなく、copyWithOperands()等のメソッ ドを使って部分木全体をコピーしなければならない。コピー対象がif文や反 復文、ブロックのように文を含む複合的なものである場合、ラベルの付け替え が必要となるので、コピーにはcopyWithOperandsChangingLabels(....)を使 う。 ５．３　LIRに対する変更 (##21) 　LIRは基本ブロックのグラフという構造をしており、基本ブロックにはL式 のリストが入っているので、部分木の改変やグラフ構造の改変も、それをそれ ぞれのプログラムで自由に変更してよい。jumpや分岐命令を変更したら、そ れに合わせてグラフ構造も変更しなければならない。すなわち、すべてがユー ザ責任となる。 ６．　アクセスメソッド 　フロー情報は、FlowRootのインスタンスflowRootをHIRまたはLIRに対し てつくり、それを用いて、副プログラムごとに controlFlowAnal を呼ぶとその副プログラムの制御フロー情報が作られ、 dataFlowAnal を呼ぶとその副プログラムのデータフロー情報が作られる。作られたフロー情 報は、 flowRoot.flow.getSubpFlow() で得られる副プログラムごとのSubpFlow、あるいは flowRoot.flow.getSubpUnderAnalysis() で得られる副プログラムからたどることができる。詳しくはFlow.java, BBlock.javaインタフェースを参照されたい。 ６．１　制御フロー情報 　制御フロー情報にアクセスする主要なメソッドの概要を示す。先行ブロック や後続ブロックのリストなど、リストを求めるメソッドでは、そのあと ListIteratorを使って個々の要素にアクセスする。 （１）副プログラムからアクセスするメソッド getEntryBBlock : 当副プログラムの入り口基本ブロック、すなわち 　　CFGの入口を求める。CFGの各ノード（基本ブロック）は、 　　SubpFlowのcfgIterator(), cfgFromExitIterator() 　　によって、深さ優先でたどることができる。深さ優先以外のやりかた 　　で基本ブロックをアクセスするには、BBlockのgetPredList()， 　　getSuccList()を使って接続関係を見て自分でアクセスする。 getFirstLoopInfList : ループ情報の木の根を求める。（一部未実装） 　　ここから、入れ子のループや兄弟ループへとアクセスする。 　　（LoopInf参照） （２）Labelからアクセスするメソッド getBBlock : 記号表のラベルからそのラベルの付与された基本ブロック 　　を求める。 （３）HIRからアクセスするメソッド 　　HIRには、任意のノードからそれを含む基本ブロックを求める 　　メソッド 　　getBBlock() 　　が用意されている。 （４）基本ブロックからアクセスするメソッド getBlockNumber : 基本ブロック番号を求める。 getIrLink : 当基本ブロックに対応するHIRまたはLIRの先頭の部分木 　　を求める。 getPredList : 先行ブロックのリストを求める。 getSuccList : 後続ブロックのリストを求める。 getPredEdge : 指定された先行ブロックへの辺を求める。 getSuccEdge : 指定された後続ブロックへの辺を求める。 getImmediateDominator : 直接に支配される基本ブロックを求める。 getDominatedChildren : 直接に支配する基本ブロックのリストを求める。 getImmediatePostDominator : 直接に逆支配される基本ブロックを求める。 getPostDominatedChildren : 直接に逆支配する基本ブロックのリストを求め る。 getFlag : フラグ番号を与えてそれに対応する情報のtrue/falseを求める。 setFlag : フラグ番号を与えてそれに対応する情報のtrue/falseを設定する。 getWork : フェーズ別情報を求める。 setWork : フェーズ別情報のインスタンスを設定する。 ６．２　データフロー情報 （１）基本ブロックからアクセスするメソッド isDef, isKill, isReach : プログラム点番号で指定された定義（値設定）が 　　Def, Kill, Reachに含まれているか否かを求める(##10)。 isDefined, isExposed, isLiveIn, isLiveOut, isDefIn, isDefOut : 　　 　　変数を指定して、それがDefined, Exposed, ... に含まれているか 　　否かを求める(##10)。 isEGen, isEKill, isAvailIn, isAvailOut : 　　式標識を指定して、それに対応する式がEGen, EKill, AvailIn, AvailOut 　　に含まれているか否かを求める(##10)。 getDef, getKill, getReach, getDefined, getExposed, getEGen, getEKill, getAvailIn, getAvailOut, getLiveIn, getLiveOut, getDefIn, getDefOut : 　　Def, Kill, ..., DefOut のビットベクトルを求める。 （２）変数とレジスタからアクセスするメソッド getDefUseList : 変数の設定・参照リストを求める。 getIndex: データプロー解析用につけた番号を求める。 （３）ビットベクトルに対するメソッド getBit : 指定番号のビット位置の０，１を見る。 setBit : 指定番号のビット位置に１を設定する。 resetBit : 指定番号のビット位置に０を設定する。 vectorAnd : ２つのビットベクトルの論理積を求める。 vectorOr : ２つのビットベクトルの論理和を求める。 vectorXor : ２つのビットベクトルの排他的論理和を求める。 vectorNot : ビットベクトルの論理否定を求める。 vectorSub : ２つのビットベクトルの差分を求める。 vectorCopy : ビットベクトルのコピーを作る。 vectorEqual : ２つのビットベクトルが等しいか否かを求める。 vectorReset : 　　 ビットベクトルの全ビットを０にする。 bitVectorInit : ビットベクトルのクラスごとにそのビット数 　　を指定してインスタンスの作成準備をするstaticメソッド。 付録　同じ式に同じ式標識を対応させることの効用 ・データフロー解析において、式に対する解析ルーチンと変数に対する解析ル ーチンを同一モジュールで実現できる。 ・同じ部分木に同じ式標識をつけるだけでは、同じ式標識でも場所によって値 が異なることになるが、これを元にして、SSAで行なうように値を設定するご とに派生名をつけてゆき、その値が伝播するところでは同じ派生名を利用する ならば、値の同じものを同じ記号で表すことができる。 ・（大域的）共通式削除の処理が簡単になる。 ・文や式を展開したとき、この式標識を一時変数として使うならば、その値を 算出する式が何であるかを直ちに知ることができる。したがって、式の計算コ ストと一時変数の利用コストを比較して、再計算した方がコストが低いとわか ったとき、任意の時点で再計算の式を復元できる。 ・もしLIRの仮想レジスタにもそれに対応する式のExpIdが何であるかという 情報を伝えてゆくならば、レジスタ割付を行ったあとでも、任意の時点でその レジスタの内容が何であるかを式として表現できる。 ・レジスタ割付に際して、レジスタを使うコストと再計算するコストを比較し て、再計算する方がよいとわかれば、再計算の命令列を容易に生成できる。 ・LIRにまでExpIdの情報を伝播させるならば、HIRから変換したL式に対し ては、それに対応するHIRの型が何であるかをExpIdにつけた型によって表現 できる。ただし、LIRに対する最適化や並列化の過程で生成されたL式の型は、 型推論の規則によって定める必要がある。 ・LIRにまでExpIdの情報を伝播させるならば、仮想レジスタの内容が何であ るかをソースプログラムに近い式として表現できるので、デバッガに対して有 用な情報を生成でき、また、コンパイラのデバッグ自体も容易になる。