翻訳と辞書
Words near each other
・ 制式名称
・ 制式番号 (ドイツ陸軍兵器局)
・ 制御
・ 制御NOTゲート
・ 制御された衝撃実演
・ 制御の反転
・ 制御キャラクタ
・ 制御コード
・ 制御システム
・ 制御フロー
制御フローグラフ
・ 制御下
・ 制御不能情動
・ 制御付振り子式車両
・ 制御付随車
・ 制御器
・ 制御因子
・ 制御工学
・ 制御性T細胞
・ 制御抽象化


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

制御フローグラフ : ウィキペディア日本語版
制御フローグラフ[せいぎょふろーぐらふ]
制御フローグラフ(せいぎょフローグラフ、)は、プログラムを実行したときに通る可能性のある全経路をグラフで表したものである。この場合、ノードは基本ブロック(すなわち、分岐を全く含まない逐次的コード列であって、途中に分岐先もない)を表し、ノードとノードをつなぐ有向エッジは、あるブロックから別ブロックへのジャンプを意味する。一般に、グラフ全体の入口となる入口ブロックと、出口となる出口ブロックがある。
CFGはコンパイラ最適化静的コード解析ツールでよく使われる。
最適化において利用されるグラフの属性として、到達可能性(reachability)がある。あるブロックまたは部分グラフが、入口ブロックを含む部分グラフと連結していない場合、そのブロックは決して実行されることはなく、いわゆる到達不能コードであって、容易に削除可能である。出口ブロックが入口ブロックから到達不能な場合、無限ループとなっている(あらゆる無限ループを検出できるわけではない。停止性問題を参照のこと)。プログラマが明示的に到達できないコードや無限ループを書かなくても、そのような状況になることはある。例えば、定数伝播定数畳み込みといった最適化を行った後に分岐スレッディングを行うと、元々は別々だった基本ブロックが1つにまとめられることがあり、エッジがCFGから除去され、グラフの一部が連結されなくなることがある。
== 用語 ==
制御フローグラフに関連して使われる用語を列挙する。
; 入口ブロック(enter block) : グラフの制御の入口となるブロック
; 出口ブロック(exit block) : グラフの制御の出口となるブロック
; 後退エッジ(back edge) : グラフを深さ優先探索したときに、上位のノードに戻るようになっているエッジ
; クリティカルエッジ(critical edge) : あるブロックから出ている唯一のエッジでもなく、あるブロックに入っている唯一のエッジでもないエッジ。このようなエッジ群は途中に新たなノード(ブロック)を追加して、そこで何からの計算が行われると考えられる。
; 異常エッジ(abnormal edge) : 行き先が不明なエッジ。最適化の妨げとなる傾向がある。例外処理によってこのようなエッジが生成される。
; 不可能エッジ(impossible edge) : 全ブロックから最終的に出口ブロックに到達するよう意図的に加えられたエッジ。実際にそこを通る制御フローは存在しない。
; 支配ノード(dominator) : ブロックMがブロックNを支配するとは、ブロックNに入っていくる全経路が必ず事前にブロックMを通っていることを意味する。入口ブロックは他の全ブロックから見て支配ノードである。
; 後支配ノード(postdominator) : ブロックNから出口ブロックまでの全経路で必ずブロックMを通るとき、ブロックMを後支配ノードと呼ぶ。出口ブロックは他の全ブロックから見て後支配ノードである。
; 直接支配ノード(immediate dominator) : ブロックMがブロックNの支配ノードで、かつその途中の経路にブロックNにとっての支配ノードが存在しない場合、ブロックMをブロックNの直接支配ノードという。あるブロックに支配ノードがある場合、直接支配ノードは唯一存在する。
; 直接後支配ノード(immediate postdominator) : 直接支配ノードと同様の考え方。
; 支配木(dominator tree) : 支配関係だけを示した補助的なデータ構造。ブロックMがブロックNの支配ノードである場合、ブロックMからブロックNへのエッジが描かれる。直接支配ノードは唯一なので、このグラフは木構造となる。根となるのは入口ブロックである。
; 後支配木(postdominator tree) : 支配木と同様。出口ブロックが根となる。
; ループヘッダ(loop header) : ループ構造の入口となるブロック。ループを構成する後退エッジが指すことになる。ループ本体を構成する全ブロックの支配ノードとなる。
; ループ前ヘッダ(loop pre-header) : ブロックMがループヘッダとする。いくつかの最適化技法では、ブロックMを Mpre と Mloop の2つに分割する。Mの中身は Mloop に移行し、後退エッジはこれを指すようにする。一方、それ以外のエッジは Mpre を指すようにし、Mpre から Mloop へのエッジを追加する(Mpre は Mloop の直接支配ノードとなる)。Mpre は当初は何もしない(コードを含まない)が、ループ不変量コード移動などの最適化でコードが移される。この Mpre をループ前ヘッダという。Mloop はループヘッダである。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「制御フローグラフ」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.