拡張基本ブロック

拡張基本ブロック(かくちょうきほんブロック、: Extended basic block[1][2]は、コンピューティングにおいて、プログラムを構成する基本ブロックの集まりを指す。最適化の対象として好適で、多くのコンパイラ最適化は拡張基本ブロックに対する操作として実現されている。

定義編集

拡張基本ブロックは以下の性質を持つ基本ブロックの集まりのうち最も大きいものである:

  • 先頭の基本ブロックだけが複数の前任者 (predecessor basic block) を持つ。
  • 他のすべての基本ブロックは1つの前任者だけを持ち、かつその前任者は当該拡張基本ブロック内にある。

使用編集

基本ブロックを操作対象とする局所最適化のうちの多くが拡張基本ブロックにも容易に適用できる。例として重複する式を排除する共通部分式除去がある。これは基本的には基本ブロックに対する操作であるが、簡単に拡張基本ブロックに対する操作に拡張できる。[3]

関連項目編集

参考文献編集

  1. ^ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 405
  2. ^ Steven S. Muchnick Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997. ISBN 1-55860-320-4 page 175
  3. ^ アーカイブされたコピー”. 2014年5月15日時点のオリジナル[リンク切れ]よりアーカイブ。2012年7月4日閲覧。

外部リンク編集