(57)【特許請求の範囲】
【請求項１】
プログラミング言語で記述されたプログラムのソース・コードを機械語に変換するコンパイラを備えたコンピュータシステムにおいて、
前記コンパイラは、
機械語に変換されたオブジェクトプログラムに対して最適化処理を行う最適化処理実行部と、
前記最適化処理実行部による最適化処理に先立って、処理対象である前記オブジェクトプログラムを当該最適化処理に適した形態に変形するプログラム変形部とを備え、
前記プログラム変形部は、前記オブジェクトプログラムが分岐を持つ場合に、当該分岐において特定のパスを選択することにより当該分岐に対する合流のない一連のパスを抜き出して、当該オブジェクトプログラムを当該一連のパスと当該一連のパスに含まれない他のパスとに分離し、当該一連のパスの一部を複製して当該他のパスに接続することを特徴とするコンピュータシステム。
【請求項２】
前記最適化処理実行部は、前記プログラム変形部により抜き出されたパスに対して最適化処理を行うことを特徴とする請求項１に記載のコンピュータシステム。
【請求項３】
前記プログラム変形部は、前記オブジェクトプログラムの分岐において、分岐後における複数のパスの実行頻度に差がある場合に、実行頻度の高いパスを選択して前記分岐に対する合流のない一連のパスを抜き出すことを特徴とする請求項１に記載のコンピュータシステム。
【請求項４】
プログラミング言語で記述されたプログラムのソース・コードを機械語に変換するコンパイラを備えたコンピュータシステムにおいて、
前記コンパイラは、
機械語に変換されたオブジェクトプログラムに分岐が存在する場合に、当該分岐において特定のパスを選択することにより、最適化の対象となる一連の最適化対象パスを決定する最適化対象パス決定部と、
前記オブジェクトプログラムのコントロールフローグラフを変形し、前記最適化対象パスと最適化の対象ではないパスとが分離されたグラフとするコントロールフローグラフ変形部と、
前記コントロールフローグラフ変形部により変形された前記コントロールフローグラフに基づいて、前記最適化対象パスに対して最適化処理を実行する最適化処理実行部と
を備えることを特徴とするコンピュータシステム。
【請求項５】
前記コントロールフローグラフ変形部は、
前記オブジェクトプログラムのコントロールフローグラフから前記最適化対象パスを抽出して前記分岐に対する合流のないパスとし、
前記最適化対象パスに含まれる部分パスを複製し、
複製された前記部分パスと前記最適化の対象ではないパスとを接続することにより、前記コントロールフローグラフを、前記最適化対象パスと、前記最適化の対象ではないパス及び前記最適化対象パスから複製された前記部分パスにて形成されるパスとで形成されたグラフに変形することを特徴とする請求項４に記載のコンピュータシステム。
【請求項６】
前記コントロールフローグラフ変形部は、
前記最適化対象パスに含まれるパスのうち、前記オブジェクトプログラムの分岐により複数のパスに分かれた箇所以外の部分パスを複製し、前記最適化の対象ではないパスと接続することを特徴とする請求項５に記載のコンピュータシステム。
【請求項７】
コンピュータによりプログラムをコンパイルするプログラム変換方法において、
前記コンピュータが、処理対象である機械語に変換されたオブジェクトプログラムに分岐が存在する場合に、当該分岐において特定のパスを選択することにより、最適化の対象となる一連の最適化対象パスを決定するステップと、
前記コンピュータが、前記オブジェクトプログラムのコントロールフローグラフを、前記最適化対象パスと最適化の対象ではない副パスとが分離されたグラフに変形するステップと、
前記コンピュータが、変形された前記コントロールフローグラフに基づいて、前記最適化対象パスに対して最適化処理を実行するステップと
を含むことを特徴とするプログラム変換方法。
【請求項８】
前記コントロールフローグラフを変形するステップは、
前記コンピュータが、前記最適化対象パスに流入している前記副パスに関して、当該副パスから流入する地点から到達可能な全ての最適化対象パスを複製するステップと、
前記コンピュータが、前記地点から前記複製されたパスまでに到達可能な全てのパスを複製するステップと、
前記コンピュータが、前記最適化対象パス内から前記副パスへの全てのエッジの接続を、前記二つのステップで複製されたパスにつなぎ換えるステップと、
前記コンピュータが、前記最適化対象パスに外から流入するエッジがあり、かつ当該エッジが前記副パスからのエッジである場合に、当該エッジの接続を前記二つのステップで複製されたパスにつなぎ換えるステップと、
前記コンピュータが、前記最適化対象パスから外へ流出するエッジがある場合に、当該エッジの始点のブロックと当該ブロックに対応する前記複製されたパス中のブロックとの合流点を作り、当該合流点からのエッジで当該最適化対象パスから外へ流出するエッジを置き換えるステップと
を含むことを特徴とする請求項７に記載のプログラム変換方法。
【請求項９】
前記コンピュータが、前記パスを複製する二つのステップにおいて、前記プログラムの分岐により複数のパスに分かれた箇所におけるパスの複製を省略することを特徴とする請求項８に記載のプログラム変換方法。
【請求項１０】
コンピュータによりプログラムをコンパイルするプログラム変換方法において、
前記コンピュータが、処理対象である前記プログラムに分岐が存在する場合に、当該分岐において特定のパスを選択することにより当該分岐に対する合流のない一連のパスを抜き出して、当該プログラムを当該一連のパスと当該一連のパスに含まれない他のパスとに分離するステップと、
前記コンピュータが、当該一連のパスの一部を複製して当該他のパスに接続するステップと、
前記コンピュータが、前記一連のパスに対して最適化処理を行うステップと
を含むことを特徴とするプログラム変換方法。
【請求項１１】
前記プログラムからパスを抜き出すステップでは、前記コンピュータが、前記プログラムの分岐において、分岐後における複数のパスの実行頻度に差がある場合に、実行頻度の高いパスを選択して、前記分岐に対する合流のない一連のパスを抜き出すことを特徴とする請求項１０に記載のプログラム変換方法。
【請求項１２】
コンピュータに実行させるプログラムを当該コンピュータの入力手段が読取可能に記憶した記憶媒体において、
コンピュータにコンパイル処理における最適化処理を実行させる前記プログラムは、
処理対象である機械語に変換されたオブジェクトプログラムに分岐が存在する場合に、当該分岐において特定のパスを選択することにより、最適化の対象となる一連の最適化対象パスを決定する処理と、
前記オブジェクトプログラムのコントロールフローグラフを、前記最適化対象パスと最適化の対象ではない副パスとが分離されたグラフに変形する処理と、
変形された前記コントロールフローグラフに基づいて、前記最適化対象パスに対して最適化処理を実行する処理と
を前記コンピュータに実行させることを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分岐を含むプログラムに対しても効果的な最適化処理を行うことが可能なコンパイラに関する。
【０００２】
【従来の技術】
通常、プログラミング言語で記述されたプログラムのソース・コードをコンパイルする際、ソースプログラムから変換された機械語のオブジェクトプログラムに対して、実際の処理効率を向上させるための最適化処理を行っている。
しかしながら、一般的に、プログラムに分岐がある場合には最適化の効果は落ちてしまう。特に、重要な最適化であるデータフロー最適化では、プログラムに分岐があると、最適化の効果が著しく落ちてしまう。データフロー最適化に用いられるデータフロー解析では、プログラムに分岐がある場合、分岐した各パスのコードの実行結果が当該分岐が合流した後に実行される動作に影響を与えてしまうことから、効率的な最適化を行うことが難しいためである。
【０００３】
プログラム中に現れる分岐の中には、実行頻度が非常に偏っており、ほとんど一方向にしか分岐しないものがある。このような分岐であっても、データフロー最適化では、頻繁に起こらない方向のパスにおけるコードの影響を全く無視することはできない。したがって、そのような頻繁に起こらないパスにおけるコードの影響を考慮して、最適化の効果が落ちてしまうこととなる。
【０００４】
従来、プログラム中に分岐が存在してもデータフロー最適化処理を実行する方法として、分岐の合流点を単純に除去する方法があった。
図１１は、この方法によりプログラムを展開する様子を示す図である。
図示のように、この方法では、分岐の合流点の後に位置する命令を複製して、各分岐のパス（合流点以前の部分）の下に置く。そして、それらの命令を各分岐のそれぞれのコンテクストに依存した特別なコードに変形する。これにより、分岐が合流せず、それぞれの分岐で分かれたまま、複数通りの処理として扱われることとなる。これにより、分岐した各パスの処理において最適化が実現され、実行速度の向上が図られる。
【０００５】
【発明が解決しようとする課題】
上述したように、プログラムのコンパイル処理で行われる最適化処理のうち、特にデータフロー最適化では、プログラム中に分岐が存在すると最適化の効果が落ちてしまう。特に、分岐における実行頻度に偏りがある場合、実際の処理においてはほとんど実行されないコードのために最適化の効果が落ちることとなる。
【０００６】
これに対して、上述した従来技術は、分岐の合流点を除去することにより最適化を実行することができるものの、プログラムにおいて複数の分岐と合流とが直列に並んでいる場合は、コード量が分岐の数に対して指数関数的に増えるという問題があった。
図１２は、複数の分岐と合流とが直列に並ぶプログラムに対して合流を除去する展開を行うことにより、コード量が急激に増大する様子を示す図である。このように、コード量が増大してしまうと、事実上、最適化処理を実行することができない。そのため、従来は、このような構造のプログラムでは、効果的な最適化を行うことができなかった。
【０００７】
そこで本発明は、複数の分岐と合流とが直列に並ぶプログラムを対象として、コード量の爆発的な増大を招くことなくデータフロー最適化処理を効果的に実行することを目的とする。
【０００８】
また本発明は、複数の分岐と合流とが直列に並ぶプログラムであって、特に当該分岐における実行頻度に差がある場合に、データフロー最適化処理を実行する上で効果的なプログラムのコントロールフローグラフを変形する方法を提供することを他の目的とする。
【０００９】
【課題を解決するための手段】
かかる目的のもと、本発明は、プログラミング言語で記述されたプログラムのソース・コードを機械語に変換するコンパイラにおいて、機械語に変換されたオブジェクトプログラムに対して最適化処理を行う最適化処理実行部と、この最適化処理実行部による最適化処理に先立って、処理対象であるオブジェクトプログラムをこの最適化処理に適した形態に変形するプログラム変形部とを備え、このプログラム変形部は、このオブジェクトプログラムが分岐を持つ場合に、この分岐において特定のパスを選択することによりこの分岐に対する合流のない一連のパスを抜き出すことを特徴としている。
分岐に対する合流のない一連のパスをオブジェクトプログラムから抜き出すことにより、分岐したパスのコードの実行結果が当該分岐の合流後における動作に影響を与えるデータフロー最適化においても、分岐を考慮することなく最適化を行うことができる。
【００１０】
ここで、この最適化処理実行部は、このプログラム変形部により抜き出されたパスに対して最適化処理を行うことを特徴としている。
最適化処理を行う対象を、オブジェクトプログラムから抜き出した、分岐に対する合流のない一連のパスとすることで、効果的な最適化を実現することができる。特に、データフロー最適化においては、分岐に対する合流のない一連のパスに対して最適化を行うことができるため、極めて効果的な最適化を実現できる。
【００１１】
ここで、このプログラム変形部は、このオブジェクトプログラムの分岐において、分岐後における複数のパスの実行頻度に差がある場合に、実行頻度の高いパスを選択してこの分岐に対する合流のない一連のパスを抜き出すことを特徴としている。
このような構成とすれば、最適化処理の対象であるパスが、分岐において実行頻度の高いパスによって構成されることとなるため、最適化されたプログラムの全体的な処理効率を大幅に向上させることができる点で優れている。
【００１２】
また、本発明は、プログラミング言語で記述されたプログラムのソース・コードを機械語に変換するコンパイラにおいて、機械語に変換されたオブジェクトプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定する最適化対象パス決定部と、このオブジェクトプログラムのコントロールフローグラフを変形し、最適化対象パスと他のパスとに分けるコントロールフローグラフ変形部と、このコントロールフローグラフ変形部により変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行する最適化処理実行部とを備えることを特徴としている。
このような構成とすれば、プログラム中から最適化処理の対象として抽出されたパスに対して最適化処理を行うため、分岐が現れる度に分岐後の合流部分の命令を複製してパスを増やす必要はない。したがって、分岐と合流とが直列に並ぶ構成のプログラムに対しても、プログラムを展開することによってコード量が急激に増加してしまう事態を回避することができる。
【００１３】
ここで、このコントロールフローグラフ変形部は、このオブジェクトプログラムのコントロールフローグラフから最適化対象パスを抽出して分岐に対する合流のないパスとし、この最適化対象パスに含まれる部分パスを複製し、複製された部分パスとこの最適化対象パスに含まれないパスとを接続することにより、このコントロールフローグラフを、最適化対象パスと、最適化対象パスに含まれないパス及び最適化対象パスから複製された部分パスにて形成されるパスとに分けることを特徴としている。
このような構成とすることにより、プログラム中から最適化対象パスを抽出した後の部分に対しても、実行可能な一連のパスを形成することができる点で好ましい。
【００１４】
さらにここで、このコントロールフローグラフ変形部は、この最適化対象パスに含まれるパスのうち、このオブジェクトプログラムの分岐により複数のパスに分かれた箇所以外の部分パスを複製し、この最適化対象パスに含まれないパスと接続することを特徴としている。
このような構成とすることにより、コントロールフローグラフを展開した後のコード量の増加を抑えることができる点で好ましい。
【００１５】
また、本発明は、プログラミング言語で記述されたプログラムのソース・コードを機械語に変換するコンパイラを備えたコンピュータシステムにおいて、このコンパイラは、機械語に変換されたオブジェクトプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定する最適化対象パス決定部と、このオブジェクトプログラムのコントロールフローグラフを変形し、最適化対象パスと他のパスとに分けるコントロールフローグラフ変形部と、このコントロールフローグラフ変形部により変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行する最適化処理実行部とを備えることを特徴としている。
このような構成とすれば、このコンピュータシステムにおいて、プログラムをコンパイルする場合に、分岐と合流とが直列に並ぶ構成のプログラムに対しても、効果的な最適化処理を行うことができる点で好ましい。
【００１６】
また、本発明は、プログラムの処理効率を向上させるための最適化を行う最適化方法において、処理対象である前記プログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定するステップと、このプログラムのコントロールフローグラフを変形し、最適化対象パスと他の副パスとに分けるステップと、変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行するステップとを含むことを特徴としている。
このような構成とすれば、分岐と合流とが直列に並ぶ構成のプログラムに対しても、プログラムを展開することによってコード量が急激に増加してしまう事態を回避することができる。
【００１７】
ここで、コントロールフローグラフを変形するステップは、最適化対象パスに流入している副パスに関して、この副パスから流入する地点から到達可能な全ての最適化対象パスを複製するステップと、この地点から複製されたパスまでに到達可能な全てのパスを複製するステップと、この最適化対象パス内からこの副パスへの全てのエッジの接続を複製されたパスにつなぎ換えるステップと、この最適化対象パスに外から流入するエッジがあり、かつこのエッジがこの副パスからのエッジである場合に、このエッジの接続を複製されたパスにつなぎ換えるステップと、この最適化対象パスから外へ流出するエッジがある場合に、このエッジの始点のブロックとこのブロックに対応する複製されたパス中のブロックとの合流点を作り、この合流点からのエッジでこの最適化対象パスから外へ流出するエッジを置き換えるステップとを含むことを特徴としている。
このような構成とすることにより、プログラム中から最適化対象パスを抽出した後の部分に対しても、実行可能な一連のパスを形成することができる点で好ましい。
【００１８】
さらにここで、パスを複製する二つのステップにおいて、プログラムの分岐により複数のパスに分かれた箇所におけるパスの複製を省略することを特徴としている。
このような構成とすることにより、コントロールフローグラフを展開した後のコード量の増加を抑えることができる点で好ましい。
【００１９】
また、本発明は、プログラムの処理効率を向上させるための最適化を行う最適化方法において、処理対象であるプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することによりこの分岐に対する合流のない一連のパスを抜き出すステップと、抜き出されたパスに対して最適化処理を行うステップとを含むことを特徴としている。
このような構成とすれば、最適化処理を行う対象を、分岐に対する合流のない一連のパスとすることができるため、特に、データフロー最適化において、極めて効果的な最適化を実現できる。
【００２０】
ここで、このプログラムからパスを抜き出すステップは、このプログラムの分岐において、分岐後における複数のパスの実行頻度に差がある場合に、実行頻度の高いパスを選択して、この分岐に対する合流のない一連のパスを抜き出すことを特徴としている。
このような構成とすれば、最適化処理の対象であるパスが、分岐において実行頻度の高いパスによって構成されることとなるため、最適化されたプログラムの全体的な処理効率を大幅に向上させることができる点で優れている。
【００２１】
また、本発明は、コンピュータにオブジェクトプログラムの最適化処理を実行させる最適化プログラムにおいて、処理対象であるオブジェクトプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定する処理と、このオブジェクトプログラムのコントロールフローグラフを変形し、最適化対象パスと他の副パスとに分ける処理と、変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行する処理とをこのコンピュータに実行させることを特徴としている。
【００２２】
さらに、本発明は、コンピュータに実行させるプログラムをこのコンピュータの入力手段が読取可能に記憶した記憶媒体において、このプログラムは、処理対象であるオブジェクトプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定する処理と、このオブジェクトプログラムのコントロールフローグラフを変形し、最適化対象パスと他の副パスとに分ける処理と、変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行する処理とをこのコンピュータに実行させることを特徴としている。
【００２３】
さらにまた、本発明は、コンピュータに、処理対象であるオブジェクトプログラムに分岐が存在する場合に、この分岐において特定のパスを選択することにより一連の最適化対象パスを決定する処理と、このオブジェクトプログラムのコントロールフローグラフを変形し、最適化対象パスと他の副パスとに分ける処理と、変形されたコントロールフローグラフに基づいて、この最適化対象パスに対して最適化処理を実行する処理とを実行させるプログラムを記憶する記憶手段と、この記憶手段からこのプログラムを読み出してこのプログラムを送信する送信手段とを備えたことを特徴としている。
これらの構成においては、このプログラムをインストールしたコンピュータをコンパイラとして動作させた際に、処理対象であるオブジェクトプログラムが分岐を持つ場合であっても、効果的な最適化処理を実現できる点で好ましい。
【００２４】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいてこの発明を詳細に説明する。
図１は、本実施の形態によるコンパイラにおける最適化処理部の構成を説明する図である。
図１において、符号１０は最適化処理部であり、機械語のオブジェクトコードに変換されたプログラムを最適化する。符号１１は最適化対象パス決定部であり、プログラムの分岐により発生した複数のパスのうち、最適化処理を施すパス（以下、最適化対象パスと称す）を決定する。符号１２はコントロールフローグラフ変形部であり、最適化対象パス決定部１１の決定に基づいて、処理対象であるプログラムのコントロールフローグラフを変形する。符号１３は最適化処理実行部であり、コントロールフローグラフ変形部１２にて変形されたコントロールフローグラフに基づいて、最適化対象パス決定部１１にて決定された最適化対象パスに対して、データフロー最適化を含む最適化処理を実行する。
【００２５】
最適化対象パス決定部１１は、処理対象であるプログラム中の分岐により複数のパスに分かれている部分において、当該複数のパスのうち、最適化処理の対象とするパスを選択する。そして、合流部分のパスと合わせて、最適化処理の対象として一本のパスを決定する。ここで、最適化対象パスは、一般的には、実行頻度の高いパス（以下、メインパスと称す）が選択される。しかしながら、厳密には、最適化対象パスは、必ずしも全てのメインパスを含んでいなくても良く、実行頻度の低いパス（以下、レアパスと称す）を含んでいてもかまわない。また、メインパスとレアパスの両方を含んでいても良い。なお、本実施の形態では、メインパスを最適化対象パスとする場合を例として説明する。
最適化対象パスの決定は、コンパイラが利用可能なリソース及び分岐の頻度、最適化スキーム等に基づいて行われる。なお、最適化対象パスの選択は、アルゴリズムの途中で動的に決定するような方式も可能である。
【００２６】
コントロールフローグラフ変形部１２は、処理対象であるプログラムのコントロールフローグラフを、最適化対象パス決定部１１により決定された最適化対象パスと、その他のパスを含むパスとに２分する。本実施の形態では、メインパスを最適化対象パスとするため、コントロールフローグラフ変形部１２により、最適化対象パスと、レアパスを含むパスとに分かれることとなる。
ここで、最適化対象パスにはメインパスと共に分岐後の合流部分のブロックが含まれているため、プログラムのコントロールフローグラフを単純に２分すると、レアパスを含む副パスは、合流部分のブロックが抜けてしまい、コード列としては不完全となる。そこで、必要なブロックの補完を行う。
【００２７】
図２は、コントロールフローグラフ変形部１２の動作を説明するフローチャートである。
図２を参照すると、まず、所定の最適化対象パスに流入しているレアパスに関して、当該レアパスから流入する地点から到達可能な全ての最適化対象パスを複製する（ステップ２０１）。
次に、上記地点から複製された最適化対象パスまでに到達可能な全てのパスを複製する（ステップ２０２）。
次に、最適化対象パス内からレアパスへの全てのエッジの接続を、複製されたパスにつなぎ換える（ステップ２０３）。
次に、最適化対象パスに外から流入するエッジがあり、かつ当該エッジがレアパスからのエッジである場合、当該エッジの接続を複製されたパスにつなぎ換える（ステップ２０４、２０５、２０６）。最適化対象パスに外から流入するエッジがない場合、及び最適化対象パスに外から流入するエッジがあっても当該エッジがレアパスからのエッジでない場合は、最適化対象パスにそのままつなげておく。
次に、最適化対象パスから外へ流出するエッジがあった場合、エッジの始点のブロックと対応する複製されたブロックとの新しい合流点を作り、その合流点からのエッジで当該エッジを置き換える（ステップ２０７、２０８）。
以上の処理を、全ての最適化対象パスに流入しているレアパスについて行う。ただし、他のレアパスに関する処理において、以前に複製を行った部分に関しては、新しい複製を作成せず、対応する部分への処理のみを行う。
【００２８】
図３は、コントロールフローグラフ変形部１２によるプログラムのコントロールフローグラフの変形例を示す図である。
図３において、太枠で示したパスが最適化対象パスである。図３（Ａ）に示すように、メインパスと合流部分ブロックとが最適化対象パスとして選択されている。変形後の状態を示す図３（Ｂ）を参照すると、ステップ２０１、２０２の処理により、破線で示した複製ブロックが生成されている。また、ステップ２０３乃至ステップ２０８の処理により、必要なエッジの接続が行われている。
【００２９】
最適化処理実行部１３は、コントロールフローグラフ変形部１２によって以上のように展開されたコントロールフローグラフに基づき、最適化処理を実行する。最適化を行う対象は最適化対象パスである。図３に示すように、最適化対象パスには分岐がないため、データフロー最適化を含め、全ての最適化処理において効果が落ちることはない。
【００３０】
したがって、最適化処理部１０の最適化対象パス決定部１１、コントロールフローグラフ変形部１２及び最適化処理実行部１３による以上の処理は、分岐を持つプログラムの中から分岐に対する合流のない一連のパスを抜き出し、その抜き出したパスにのみ最適化処理を施すことに相当する。最適化されたプログラムを実行する場合、当該最適化処理を施されたパスに沿って処理を実行する場合は、当該最適化により処理効率の向上を図ることができる。一方、その他のパスに沿って処理を実行する場合は、処理効率の向上は望めない。ただし、図３に示したように複数の分岐と合流とが直列に並んだプログラムでは、合流点を除去する従来の方法では事実上最適化処理を実行することができないので、殊更この場合のプログラムの処理効率がその場合の処理効率と同等となる。
【００３１】
また、図３（Ｂ）に示すように、最適化対象パスにおいて、コントロールフローグラフの変形前に分岐のあった部分からは、レアパスへのエッジが接続されている。これに対し、コントロールグラフの変形前に合流のあった部分へのエッジは存在しない。したがって、最適化対象パスに沿ってプログラムを実行する際に、分岐において、レアパスを含むパスに沿った処理に移行したならば、以後の処理は当該レアパスを含むパスに沿って、すなわち、最適化されていない状態のプログラムを実行することとなる。
【００３２】
以上のように、本実施の形態では、分岐と合流とが含まれるプログラムをコントロールフローグラフにおいて展開し、分岐に対する合流を除去した最適化処理対象パスを得、当該最適化処理対象パスに対して最適化を行う。したがって、分岐が存在するプログラムでは最適化の効果が著しく落ちてしまうデータフロー最適化においても、その効果を落とすことなく最適化を行うことが可能となる。
【００３３】
また、本実施の形態では、分岐を持つプログラム中から最適化処理の対象となるパスを抽出し、他のパスについては最適化の適用を考慮しないため、全ての分岐ごとにプログラムを展開する必要がない。したがって、プログラムにおいて分岐と合流とが直列に並んでいる場合であっても、コード量が指数関数的に急激に増加してしまうことはない。
【００３４】
さらに、本実施の形態では、上述したように、実行頻度の高いメインパスを選択して最適化対象パスを形成している。このため、図３（Ｂ）のように変形されたプログラムを実行する場合、ほとんどの場合の処理は最適化されたパスに沿って実行され、例外的にレアパス側に処理が移行した場合にのみ、以後の処理が最適化されていないパスに沿って実行されることとなる。したがって、全体的な処理効率を大幅に向上させることが可能となる。
【００３５】
ところで、実行頻度に偏りがある分岐を含むプログラムの特殊な形態として、メインパスの処理がレアパスに含まれているものがある。例えば
if(a==0) then A else B
のような場合に、Ｂの処理がａ＝０のときも考慮した一般的な記述になっている場合である。このようなケースは、オブジェクト指向言語の最適化コンパイラにおけるデバーチャライゼーション時に現れる。
このような性質を持った分岐を扱う場合は、レアパスに移行した際は、以後の処理はレアパス及び合流部分のブロックに沿って実行すれば良いため、合流部分のブロックのみをレアパス側に複製し、メインパスは二重化しない。これにより、コード量を小さく抑えることができる。
【００３６】
図４は、このようにメインパスを複製しない場合のコントロールフローグラフの変形例を示す図である。
図４と図３とを比較すると、最適化対象パスは同一で、メインパスと合流部分のブロックとで形成されている。一方、レアパスを含むパスは、合流部分のブロックの複製ブロックとレアパスのみで形成されており、メインパスは複製されていない。したがって、レアパスを含むパスにおいて分岐は存在せず、最適化対象パスから流入するエッジ（合流）のみが存在している。
【００３７】
図５は、本実施の形態におけるコントロールフローグラフの変形処理の実施アルゴリズムを説明するフローチャートである。
本アルゴリズムが対象とする分岐は全て、メインパスの処理がレアパスの処理に含まれているものとする。また、最適化パスの選択はアルゴリズムの中でインクリメンタルに行われている。すなわち、上述した最適化パスを以下の複製対象に換えて、繰り返し処理を行ったものと考えてよい。
【００３８】
図５を参照すると、まず、所定のメインパスとレアパスの合流点から直接到達可能なメインパスとレアパスの分岐点を検出する（ステップ５０１）。そのような分岐点が検出されなければ終了する。
次に、合流点と検出された分岐点とを結ぶ全てのパスを検出する（ステップ５０２）。以下、検出されたパスを複製対象パスと呼ぶ。
次に、複製対象パス上のブロックとエッジを複製する（ステップ５０３）。
次に、合流点を削除し、合流点に流入していたメインパスを複製対象パスにつなぐ。また、同じく合流点に流入していたレアパスを複製されたパスにつなぐ（ステップ５０４）。
次に、複製されたパスを、レアパスへの分岐につなぐ（ステップ５０５）。
複製対象パスに外から流入するエッジがあり、当該エッジがレアパスからのエッジだった場合、複製されたパスにつなぎ換える（ステップ５０６、５０７、５０８）。複製対象パスに外から流入するエッジがない場合、または外から流入するエッジがあっても当該エッジがレアパスからのエッジでない場合は、複製対象パスにそのままつなげておく。
また、複製対象パスから外へ流出するエッジがあった場合、エッジの始点のブロックと対応する複製されたブロックとの新しい合流点を作り、その合流点からのエッジで上記エッジを置き換える（ステップ５０９、５１０）。
以上の処理を、再帰的に繰り返してコントロールフローグラフが変形される。
【００３９】
図６乃至図１０は、図５を参照して説明した実施アルゴリズムの適用例を示す図である。
図６において、まず、合流点２と合流点２から直接到達可能な分岐点３とに着目し（ステップ５０１）、合流点２から分岐点３までのパスを複製対象パスとする（ステップ５０２）。
そして、合流点２と分岐点３との間のパスに沿ったブロックＤとブロックＥとを複製し、複製されたブロックＤ’から複製されたブロックＥ’にエッジをつなぐ（ステップ５０３）。ブロックＥ’からは、分岐点３ではなく、分岐点３から分岐したブロックＧに直接エッジをつなぐ（ステップ５０４）。Ｅに外から流入するエッジは、レアパスからのエッジではないので、何ら処理を行わない。
【００４０】
次に、合流点４からのパスにおいて複製できる候補は二つある。したがって、これ以降の変形には二つの手順がある。
一つは、合流点４から分岐点３までのパスを複製する場合である。図７及び図８は、この場合のコントロールフローグラフの変形を示す図である。
図７を参照すると、まず、このパスに沿ったブロックＨとブロックＥとを複製する（ステップ５０３）。ただし、ブロックＥについては、処理がここから始まる場合には複製する必要があるが、前の段階で既に複製されている場合は複製する必要はない。次に、複製されたブロックＨ’から複製されたブロックＥ’にエッジをつなぐ（ステップ５０３）。ブロックＩにつながるエッジは外に流出するエッジであるので、新しい合流点を一つ作り、ブロックＨ，Ｈ’からのエッジをつなぐ（ステップ５１０）。
【００４１】
次に、図８を参照すると、図７の状態のコントロールフローグラフから合流点４から分岐点５までパスに沿ったブロックＩを複製する（ステップ５０３）。そして、ブロックＨ’からブロックＩ’にエッジをつなぐ（ステップ５０４）。また、ブロックＩ’からは、分岐点５ではなく、分岐点５から分岐したブロックＫに直接エッジをつなぐ（ステップ５０４）。
【００４２】
もう一つの変形手順は、合流点４から分岐点５までのパスを複製する場合である。図９及び図１０は、この場合のコントロールフローグラフの変形を示す図である。
図９を参照すると、まず、このパスに沿ったブロックＨとブロックＩとを複製し、複製したブロックＨ’から複製したブロックＩ’にエッジをつなぐ（ステップ５０３）。ブロックＩ’からは、分岐点５ではなく、分岐点５から分岐したブロックＫに直接エッジをつなぐ（ステップ５０８）。また、ブロックＥにつながるエッジは外に流出するエッジであるので、新しい合流点を一つ作り、ブロックＨ，Ｈ’からのエッジをつなぐ（ステップ５１０）。
【００４３】
次に、図１０を参照すると、合流点４と分岐点２の間のパスに沿ったブロックＥを複製する（ステップ５０３）。ただし、前段階までで複製が行われているので、ここでは、ブロックＨ’からブロックＥ’までのエッジが張られるのみである。また、Ｅに外から流入するエッジがあるが、これはレアパスからのエッジではないので、何ら処理を行わない。
【００４４】
図８及びず１０を参照すると、合流点４から分岐点３までのパスを複製する手順（図７、図８）で変形を行っても、合流点４から分岐点５までのパスを複製する手順（図９、図１０）で変形を行っても、最終的に得られるコントロールフローグラフは同一である。
【００４５】
以上のようにして、図６に示したコントロールフローグラフが、メインパスからなる最適化対象パスＡ−Ｂ−Ｄ−Ｅ−Ｆ−Ｈ−Ｉ−Ｊ−Ｌと、レアパスからなる最適化の効果が考慮されないパスＡ−Ｃ−Ｄ’−Ｅ’−Ｇ−Ｈ’−Ｉ’−Ｋ−Ｌとに展開される。この後、最適化処理実行部１３において、最適化対象パスＡ−Ｂ−Ｄ−Ｅ−Ｆ−Ｈ−Ｉ−Ｊ−Ｌに対する最適化処理が行われる。
【００４６】
【発明の効果】
以上説明したように、本発明によれば、複数の分岐と合流とが直列に並ぶプログラムを対象として、コード量の爆発的な増大を招くことなくデータフロー最適化処理を実行することができる。
【００４７】
また、本発明によれば、複数の分岐と合流とが直列に並ぶプログラムであって、特に当該分岐における実行頻度に差がある場合に、データフロー最適化処理を実行する上で効果的なプログラムのコントロールフローグラフを変形する方法を提供することができる。
【図面の簡単な説明】
【図１】  本実施の形態によるコンパイラにおける最適化処理部の構成を説明する図である。
【図２】  本実施の形態におけるコントロールフローグラフ変形部の動作を説明するフローチャートである。
【図３】  本実施の形態のコントロールフローグラフ変形部によるプログラムのコントロールフローグラフの変形例を示す図である。
【図４】  本実施の形態におけるメインパスを複製しない場合のコントロールフローグラフの変形例を示す図である。
【図５】  本実施の形態におけるコントロールフローグラフの変形処理の実施アルゴリズムを説明するフローチャートである。
【図６】  図５に示したコントロールフローグラフの変形処理の実施アルゴリズムの適用例を示す図であり、合流点２から分岐点３までのパスに着目して変形する様子を示す図である。
【図７】  図５に示したコントロールフローグラフの変形処理の実施アルゴリズムの適用例を示す図であり、合流点４から分岐点３までのパスに着目して変形する様子を示す図である。
【図８】  図５に示したコントロールフローグラフの変形処理の実施アルゴリズムの適用例を示す図であり、合流点４から分岐点３までのパスに着目してさらに変形する様子を示す図である。
【図９】  図５に示したコントロールフローグラフの変形処理の実施アルゴリズムの適用例を示す図であり、合流点４から分岐点５までのパスに着目して変形する様子を示す図である。
【図１０】  図５に示したコントロールフローグラフの変形処理の実施アルゴリズムの適用例を示す図であり、合流点４から分岐点５までのパスに着目してさらに変形する様子を示す図である。
【図１１】  従来の分岐の合流点を単純に除去する方法によりプログラムを展開する様子を示す図である。
【図１２】  複数の分岐と合流とが直列に並ぶプログラムに対して、従来の合流を除去する展開を行うことにより、コード量が急激に増大する様子を示す図である。
【符号の説明】
１０…最適化処理部、１１…最適化対象パス決定部、１２…コントロールフローグラフ変形部、１３…最適化処理実行部
【図１】
0003651579.tif 000002
【図２】
0003651579.tif 000003
【図３】
0003651579.tif 000004
【図４】
0003651579.tif 000005
【図５】
0003651579.tif 000006
【図６】
0003651579.tif 000007
【図７】
0003651579.tif 000008
【図８】
0003651579.tif 000009
【図９】
0003651579.tif 000010
【図１０】
0003651579.tif 000011
【図１１】
0003651579.tif 000012
【図１２】
0003651579.tif 000013