【手続補正書】
【提出日】令和2年12月28日(2020.12.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ソースコードコンピュータプログラムをオブジェクトコードコンピュータプログラムに変換するコンパイルデバイスであって、
ソースコードコンピュータプログラムを受信する入力部と、
前記ソースコードコンピュータプログラムを解析し、前記ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフを生成するプロセッサ回路と、
を含み、
前記ＳＳＡグラフの頂点が、演算に対応し、前記ＳＳＡの辺が、代入に対応し、前記辺は、当該辺が対応する前記代入に対応するビットサイズを有し、
前記入力部は更に、前記ＳＳＡグラフの空ではない第１の部分グラフの指示を受信し、
前記指示は、前記ソースコードコンピュータプログラムの１つ以上の変数及び／又は代入を含み、指示された前記第１の部分グラフは、前記１つ以上の変数及び／又は代入に対応する辺を含み、前記第１の部分グラフは、中間値が前記コンピュータプログラム内で明示的に表されないことが望ましい前記ＳＳＡグラフの一部を表し、
前記プロセッサ回路は更に、
前記ＳＳＡグラフの第２の部分グラフを探索し、
前記ＳＳＡグラフの前記第２の部分グラフを、前記オブジェクトコードコンピュータプログラムに、単一の演算として実装させて、これにより、前記第１の部分グラフの辺に対応する代入を省略し、
前記第１の部分グラフは、前記第２の部分グラフの部分グラフであり、前記第２の部分グラフの流入辺に対応するビットサイズの合計が、前記第１の部分グラフの流入辺に関連付けられるビットサイズの合計よりも小さい、コンパイルデバイス。
【請求項２】
前記プロセッサ回路は、前記第１の部分グラフの複数のスーパーグラフにわたって反復し、前記複数のスーパーグラフから、前記第２の部分グラフの流入辺に関連付けられるビットサイズの最小合計を有するスーパーグラフを前記第２の部分グラフとして選択するか、又は、前記最小合計が前記第１の部分グラフの流入辺に関連付けられるビットサイズの前記合計よりも大きい場合、前記第１の部分グラフと等しい前記第２の部分グラフを選択する、請求項１に記載のコンパイルデバイス。
【請求項３】
前記第２の部分グラフを探索することは、最小カットアルゴリズムを適用することを含む、請求項１に記載のコンパイルデバイス。
【請求項４】
前記ＳＳＡグラフの前記第２の部分グラフは、前記オブジェクトコードコンピュータプログラムに、テーブル又はテーブルネットワークとして実装される、請求項１から３の何れか一項に記載のコンパイルデバイス。
【請求項５】
前記ＳＳＡグラフの前記第２の部分グラフは、前記オブジェクトコードコンピュータプログラムに、アフィン変換として実装される、請求項１から４の何れか一項に記載のコンパイルデバイス。
【請求項６】
前記ＳＳＡグラフ内の前記第２の部分グラフは、修正されていないＳＳＡグラフ内の第２の部分グラフによって示されているのと同じ演算を修正されたＳＳＡグラフ内に示す、前記修正されたＳＳＡグラフ内の単一の頂点に置換される、請求項１から５の何れか一項に記載のコンパイルデバイス。
【請求項７】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ＳＳＡグラフの１つ以上の辺の指示を含み、前記プロセッサ回路は、前記複数の指示された辺のうちの第１の辺と、指示された辺からなる前記ＳＳＡグラフ内のパスを介して前記第１の辺と連結する前記複数の指示された辺の全ての更なる辺とを選択する、請求項１から６の何れか一項に記載のコンパイルデバイス。
【請求項８】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ソースコードコンピュータプログラム内の変数の指示を含み、前記プロセッサ回路は、指示された前記変数への代入を、前記ＳＳＡグラフ内の辺として表し、表された前記辺は、前記ＳＳＡグラフの複数の辺の前記指示に含まれる、請求項７に記載のコンパイルデバイス。
【請求項９】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ソースコードコンピュータプログラムの一部の指示を含み、前記プロセッサ回路は、前記ソースコードコンピュータプログラムの指示された前記一部における代入を、開始辺、中間辺及び終了辺を含むパスとして表し、前記開始辺及び前記終了辺は、前記複数の指示された辺に含まれ、前記中間辺は前記複数の指示された辺に含まれない、請求項８に記載のコンパイルデバイス。
【請求項１０】
前記テーブル又は前記テーブルネットワークは、符号化データに作用する、請求項４に従属する請求項９に記載のコンパイルデバイス。
【請求項１１】
前記プロセッサ回路は、
前記ＳＳＡグラフから派生グラフを生成し、
前記派生グラフに最小カットアルゴリズムを適用して、前記派生グラフの２つの部分グラフへの分割を得て、
前記派生グラフは、
前記第１の部分グラフの流入辺を含む有向パスを介して前記第１の部分グラフに連結される前記ＳＳＡグラフ内の前記頂点及び前記辺と、
前記ＳＳＡグラフ内の流入辺を持たない頂点に、無限大のビットサイズの辺で連結されるソース頂点と、
前記第１の部分グラフの前記頂点の少なくとも一部と、
前記第１の部分グラフ内の前記頂点のうちの少なくとも１つの頂点に、無限大のビットサイズの辺で連結されるシンク頂点と、
を含み、
前記２つの部分グラフのうちの第１の部分グラフは、前記ソース頂点を含み、前記２つの部分グラフのうちの第２の部分グラフは、前記シンク頂点を含み、
前記ＳＳＡグラフ内の前記第２の部分グラフを、第２の分割内の前記頂点に対応する部分グラフとして得る、請求項１から１０の何れか一項に記載のコンパイルデバイス。
【請求項１２】
前記ＳＳＡグラフからの前記派生グラフは、前記第１の部分グラフの辺を含まず、前記シンク頂点は、前記第１の部分グラフの全ての頂点に、無限大のビットサイズの辺で連結されるか、又は、
前記ＳＳＡグラフからの前記派生グラフは、前記第１の部分グラフの辺を含み、前記辺のビットサイズは、無限大に設定されている、請求項１１に記載のコンパイルデバイス。
【請求項１３】
記ＳＳＡグラフの更なる部分グラフの更なる指示を受信し、前記プロセッサ回路は更に、前記第２の部分グラフを探索する前に、前記更なる部分グラフ内の辺のビットサイズを無限大に設定する、請求項１から１２の何れか一項に記載のコンパイルデバイス。
【請求項１４】
ソースコードコンピュータプログラムをオブジェクトコードコンピュータプログラムに変換するコンパイル方法であって、
ソースコードコンピュータプログラムを受信するステップと、
前記ソースコードコンピュータプログラムを解析するステップと、
前記ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフを生成するステップと、
前記ＳＳＡグラフの空でない第１の部分グラフの指示を受信するステップと、
前記ＳＳＡグラフの第２の部分グラフを探索するステップと、
前記ＳＳＡグラフの前記第２の部分グラフを、前記オブジェクトコードコンピュータプログラムに、単一の演算として実装させて、前記第１の部分グラフの辺に対応する代入を省略するステップと、
を含み、
前記ＳＳＡグラフの頂点が、演算に対応し、前記ＳＳＡの辺が、代入に対応し、前記辺は、当該辺が対応する前記代入に対応するビットサイズを有し、、
前記指示は、前記ソースコードコンピュータプログラムの１つ以上の変数及び／又は代入を含み、指示された前記第１の部分グラフは、前記１つ以上の変数及び／又は代入に対応する辺を含み、前記第１の部分グラフは、中間値が前記コンピュータプログラム内で明示的に表されないことが望ましい前記ＳＳＡグラフの一部を表し、
前記第１の部分グラフは、前記第２の部分グラフの部分グラフであり、前記第２の部分グラフの流入辺に対応するビットサイズの合計が、前記第１の部分グラフの流入辺に関連付けられるビットサイズの合計よりも小さい、方法。
【請求項１５】
プロセッサシステムに請求項１４に記載の方法を行わせる命令を表す一時的又は非一時的データを含む、コンピュータ可読媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
図１ａから図５ｅにおける参照符号のリスト
１００  コンパイルデバイス
１０２  ソースコードコンピュータプログラム
１０４  ＳＳＡグラフの第１の部分グラフ（Ｎ）の指示
１０６  オブジェクトコードコンピュータプログラム
１１０  入力部
１２０  パーサ
１２２  第１の静的単一代入（ＳＳＡ）グラフ
１３０  探索ユニット
１３２  第２のグラフセレクタ
１３３  ＳＳＡグラフモディファイア
１３４  制御フロー
１３６  第２のＳＳＡグラフ
１３７  置換された第２の部分グラフの実装に関する情報
１４０  コード生成器
２００  探索ユニット
２１０  派生ＳＳＡグラフ生成器
２２０  最小カットソルバー
２３０  ＳＳＡグラフモディファイア
３１０  分配ノード
３２０、３３０  頂点
３２０’、３３０’  頂点
３２２、３２４  頂点
５０１〜５１６  頂点
５２０  ソース
５３０  シンク
５４０  追加された頂点
５７０  最小カット解
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
図５ａから図５ｅを参照して、最小カットアルゴリズムの実施形態を説明する。図５ａに、例示的なＳＳＡグラフを示す。例えば図５ａのＳＳＡグラフは、ソースコード１０２の一部を表す。図５ａでは、ボックスを使用して引数（例えば入力）を表し、小さい白丸を使用して出力を表し、小さい黒丸を使用して頂点を表す。辺は、対応する変数のビットサイズがラベル付けされている。図５ａは、ノード５０１〜５１５を示す。図５ａはまた、破線の辺で示されている第１の部分グラフを示す。この例における第１の部分グラフは、頂点５０８、５１５及び５１６によって形成されている。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
派生グラフを作成する両方の例において、第１の部分グラフにない任意の非表示辺のビットサイズもまた無限大に設定される。１つの実装では、多くの非連結部分グラフがありうるが、このような追加の非表示辺は、図５ａから図５ｅにはない。例えばＳＳＡグラフの非表示にされるべき更なる部分グラフの更なる指示が受け取られていてもよい。なお、これは、更なる部分グラフが第２の部分グラフに完全に含まれる解を排除しない。これは問題ではない。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
図４ａから図４ｃは、更に別の例を示す。図４ａは、非表示変数を有するソースコードプログラム断片を示す。図４ｂは、点線で非表示プロパティを有する辺を示す。図４ｃは、テーブル挿入後の状態を示す。