(57)【要約】      （修正有）【課題】キャッシュミスが発生しにくいレジスタ退避を実現する。【解決手段】コンパイル装置４は、コードを，仮想レジスタに割り当てるユニット４ａ、仮想レジスタのレジスタ生存区間がスカラ使用タイプかＳＩＭＤ使用タイプか判断するユニット４ｂ、レジスタ生存区間が実レジスタに割り当て可能か判断するユニット４ｃ、レジスタ生存区間が実レジスタに割り当て可能な場合、レジスタ生存区間を実レジスタに割り当てるユニット４ｄ、レジスタ生存区間が実レジスタに割り当て可能ではなくレジスタ生存区間がスカラ使用タイプと判断された場合に退避用ＳＩＭＤ実レジスタを確保するユニット４ｅ、退避用ＳＩＭＤ実レジスタが確保された場合にレジスタ生存区間を退避用ＳＩＭＤ実レジスタに割り当て、残りのレジスタ生存区間を実レジスタに割り当て、レジスタ生存区間と残りのレジスタ生存区間の境界にレジスタ退避コードを割り当てるユニット４ｆを具備する。【選択図】図１
2008009957.tif 000002
【特許請求の範囲】
【請求項１】
コードを、無限の記憶領域を持つ仮想レジスタに割り当てる第１割り当て部と、
前記仮想レジスタにおけるレジスタ生存区間が、スカラ使用タイプか、ＳＩＭＤ使用タイプか判断する第１判断部と、
前記レジスタ生存区間が、実レジスタに割り当て可能か判断する第２判断部と、
前記レジスタ生存区間が、前記実レジスタに割り当て可能な場合、前記レジスタ生存区間を、前記実レジスタに割り当てる第２割り当て部と、
前記レジスタ生存区間が前記実レジスタに割り当て可能ではなく、前記レジスタ生存区間がスカラ使用タイプと判断された場合に、退避用ＳＩＭＤ実レジスタを確保する確保部と、
前記確保部によって前記退避用ＳＩＭＤ実レジスタが確保された場合に、前記レジスタ生存区間の一部又は全部の生存区間を前記退避用ＳＩＭＤ実レジスタに割り当て、前記レジスタ生存区間の残りの生存区間を前記実レジスタに割り当て、前記レジスタ生存区間の一部又は全部の生存区間と前記レジスタ生存区間の残りの生存区間との境界にレジスタ退避コードを割り当てる第３割り当て部と
を具備するコンパイル装置。
【請求項２】
前記第１判断部は、前記レジスタ生存区間が前記スカラ使用タイプの場合、前記レジスタ生存区間にフラグを付し、
前記確保部は、前記レジスタ生存区間が前記実レジスタに割り当て可能ではなく、前記レジスタ生存区間に前記フラグが付されている場合に、前記退避用ＳＩＭＤ実レジスタを確保する
ことを特徴とする請求項１記載のコンパイル装置。
【請求項３】
前記第３割り当て部は、前記レジスタ生存区間における前記スカラ使用タイプと判断された部分を、前記レジスタ生存区間における前記ＳＩＭＤ使用タイプと判断された部分よりも優先して選択し、前記スカラ使用タイプと判断された部分を前記退避用ＳＩＭＤ実レジスタに割り当てる
ことを特徴とする請求項１記載のコンパイル装置。
【請求項４】
前記第３割り当て部は、前記レジスタ生存区間における前記スカラ使用タイプと判断された部分の重み値が、前記レジスタ生存区間における前記ＳＩＭＤ使用タイプと判断された部分の重み値よりも大きい場合に、前記スカラ使用タイプと判断された部分を前記退避用ＳＩＭＤ実レジスタに割り当てる
ことを特徴とする請求項１記載のコンパイル装置。
【請求項５】
前記第３割り当て部は、前記レジスタ生存区間の一部又は全部の生存区間を、前記退避用ＳＩＭＤ実レジスタの未使用領域に割り当てる
ことを特徴とする請求項１記載のコンパイル装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル装置に関する。
【背景技術】
【０００２】
特許文献１（特開平６−１３９０６９号公報）の第３ページ左欄第１８行から第３５行には、命令は、レジスタデータの一部を読み出すためのアドレスフィールドとデータサイズフィールドとを持つことが記載されている。
【０００３】
特許文献２（特開平９−９１１５１号公報）の第３ページ左欄第１７行から第３７行には、コンパイラ及びプロセッサは、ＩＳＡでアクセスされるレジスタの不足によって引き起こされるメモリアクセスを減少するために、ＩＳＡによってアクセスできないレジスタを用いることが記載されている。
【特許文献１】特開平６−１３９０６９号公報
【特許文献２】特開平９−９１１５１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、キャッシュミスが発生しにくいレジスタ退避（register spilling）を実現することを目的とする。
【課題を解決するための手段】
【０００５】
本願発明の一態様によれば、コンパイル装置は、コードを、無限の記憶領域を持つ仮想レジスタに割り当てる第１割り当て部と、仮想レジスタにおけるレジスタ生存区間が、スカラ使用タイプか、ＳＩＭＤ使用タイプか判断する第１判断部と、レジスタ生存区間が、実レジスタに割り当て可能か判断する第２判断部と、レジスタ生存区間が、実レジスタに割り当て可能な場合、レジスタ生存区間を、実レジスタに割り当てる第２割り当て部と、レジスタ生存区間が実レジスタに割り当て可能ではなく、レジスタ生存区間がスカラ使用タイプと判断された場合に、退避用ＳＩＭＤ実レジスタを確保する確保部と、確保部によって退避用ＳＩＭＤ実レジスタが確保された場合に、レジスタ生存区間の一部又は全部の生存区間を退避用ＳＩＭＤ実レジスタに割り当て、レジスタ生存区間の残りの生存区間を実レジスタに割り当て、レジスタ生存区間の一部又は全部の生存区間と残りの生存区間の境界にレジスタ退避コードを割り当てる第３割り当て部とを具備する。
【発明の効果】
【０００６】
本発明においては、キャッシュミスが発生しにくいレジスタ退避を実現することができる。
【発明を実施するための最良の形態】
【０００７】
以下、図面を参照しながら本発明の各実施の形態について説明する。
【０００８】
（第１の実施の形態）
図１は、本実施の形態に係るコンパイル装置の一例を示すブロック図である。
【０００９】
プロセッサ１は、記憶装置２に記憶されているコンパイラ３を読み出して実行することにより、コンパイル装置４として機能する。プロセッサ１は、ＳＩＭＤ(Single Instruction Multiple Data）実レジスタ５ａ、スカラ実レジスタ５ｂを含む実レジスタ５を具備する。
【００１０】
コンパイル装置４は、記憶装置２に記憶されているソースプログラムコード６を機械語コード７に変換し、この機械語コード７を実レジスタ５に割り当てる。
【００１１】
本実施の形態に係るコンパイル装置４は、ＳＩＭＤ実レジスタ５ａ上に、スカラ命令を割り当てる場合に、ＳＩＭＤ実レジスタ５ａの未使用領域をレジスタ退避領域として選択する。
【００１２】
ＳＩＭＤ実レジスタ５ａは、例えば、ＳＩＭＤ命令を格納可能な広い幅のレジスタ（wide width register （例えば１２８ bits width)）である。ＳＩＭＤ命令は、複数のデータと対応付けられており、ＳＩＭＤ命令に対しては、広いデータ格納領域が必要となる。
【００１３】
スカラ命令のデータ格納領域は、ＳＩＭＤ命令のデータ格納領域よりも少なくてよい。
【００１４】
プロセッサ１は、ＳＩＭＤ実レジスタ５ａを必要とするＳＩＭＤ機能を持つ。プロセッサ１に対するコードは、狭い幅のデータを必要とするスカラ命令と、広い幅のデータを必要とするＳＩＭＤ命令との両方を具備する。
【００１５】
コンパイル装置４において、レジスタ退避コードは、マッピングにおいて実レジスタ５の数が十分でない場合に、コンパイル結果の機械語コード７に挿入される。
【００１６】
レジスタ退避コードは、退避された実レジスタ５のデータをセーブ及びリストアするためのストア命令及びロード命令を具備する。
【００１７】
コンパイル装置４によるコンパイルにおいて、スカラ命令に対してレジスタ退避を行う場合、レジスタ退避領域は、実レジスタ５内の他の記憶内容に影響を与えない領域とする。
【００１８】
ＩＳＡ（Instruction Set Architecture）がＧＰＲ（汎用レジスタ）とＳＩＭＤ実レジスタとの間で移動されるデータを認めている又はＧＰＲ自身がＳＩＭＤ実レジスタであり、かつ他の領域が影響を受けることなくＳＩＭＤデータの一部を他のＳＩＭＤ実レジスタの特定の領域に移動する命令があれば、レジスタ退避コードは、レジスタ退避エリアとしてＳＩＭＤ実レジスタ５ａの未使用領域を使用するように改良可能である。
【００１９】
本実施の形態において、コンパイル装置４は、第１割り当て部４ａ、第１判断部４ｂ、第２判断部４ｃ、第２割り当て部４ｄ、確保部４ｅ、第３割り当て部４ｆを具備する。
【００２０】
第１割り当て部４ａは、コードを、無限の記憶領域を持つ仮想レジスタに割り当てる。
【００２１】
第１判断部４ｂは、仮想レジスタにおけるレジスタ生存区間が、スカラ使用タイプか、ＳＩＭＤ使用タイプか判断する。
【００２２】
第２判断部４ｃは、レジスタ生存区間が、実レジスタに割り当て可能か判断する。
【００２３】
第２割り当て部４ｄは、レジスタ生存区間が、実レジスタ５に割り当て可能な場合、レジスタ生存区間を、実レジスタ５に割り当てる。
【００２４】
確保部４ｅは、レジスタ生存区間が実レジスタ５に割り当て可能ではなく、レジスタ生存区間がスカラ使用タイプと判断された場合に、退避用ＳＩＭＤ実レジスタを確保する。
【００２５】
第３割り当て部４ｆは、確保部４ｅによって退避用ＳＩＭＤ実レジスタが確保された場合に、レジスタ生存区間の一部又は全部の生存区間を退避用ＳＩＭＤ実レジスタに割り当て、レジスタ生存区間の残りの生存区間を実レジスタ５に割り当て、レジスタ生存区間の一部又は全部の生存区間とレジスタ生存区間の残りの生存区間との境界にレジスタ退避コードを割り当てる。
【００２６】
図２は、本実施の形態に係るコンパイル装置４によるレジスタ割り当てアルゴリズムの一例を示すフローチャートである。
【００２７】
ステップＳ１において、第１割り当て部４ａは、例えばＣ言語などのような高級プログラミング言語によって記述されたソースプログラムコードを、機械語コードに変換し、無限の領域を持つ仮想レジスタに割り当てる。
【００２８】
ステップＳ２において、第１判断部４ｂは、すべての仮想レジスタにおけるレジスタ生存区間（レジスタ使用領域）を計算し、各レジスタ生存区間のタイプがスカラ使用タイプに該当するかＳＩＭＤ使用タイプに該当するか判断し、スカラ使用タイプに相当する仮想レジスタにおけるレジスタ生存区間に対して、フラグＳを付す。
【００２９】
ステップＳ３において、第２判断部４ｃは、グラフカラーリング技法を用いて、実レジスタ５に、仮想レジスタにおけるレジスタ生存区間の割り当てを試みる。
【００３０】
ステップＳ４において、第２判断部４ｃは、すべての仮想レジスタにおけるレジスタ生存区間を、実レジスタ５に割り当てることができたか否か判断する。
【００３１】
すべての仮想レジスタにおけるレジスタ生存区間が、実レジスタに割り当てられている場合、ステップＳ５において、第２割り当て部４ｄは、仮想レジスタにおけるレジスタ生存区間のコードを、実レジスタ５に割り当てる。そして、レジスタ割り当て処理は終了する。
【００３２】
実レジスタ５に割り当て可能でない仮想レジスタにおけるレジスタ生存区間が存在する場合、例えば、実レジスタ５の数が、仮想レジスタにおけるレジスタ生存区間の数よりも少ない（shorter）場合、ステップＳ６において、確保部４ｅは、実レジスタ５におけるレジスタ生存区間となる領域を確保するとともに、退避用ＳＩＭＤ実レジスタ５ａにおけるレジスタ生存区間となる領域を確保する。
【００３３】
ステップＳ７において、第３割り当て部４ｆは、確保された実レジスタ５にコードを割り当てるとともに、確保された退避用ＳＩＭＤ実レジスタ５ａに、仮想レジスタにおけるレジスタ生存区間のうちのいずれかの退避を行う。
【００３４】
上記ステップＳ６において、フラグＳの付された仮想レジスタにおけるレジスタ生存区間は、退避されるレジスタとしての優先権を持つ。
【００３５】
フラグＳの付された仮想レジスタにおけるレジスタ生存区間の中で、使用回数が少なく、仮想レジスタにおいて区間の大きいレジスタ生存区間が、退避対象として選択される。
【００３６】
フラグＳの付された仮想レジスタにおけるレジスタ生存区間が退避されるために選択されたが、退避用ＳＩＭＤ実レジスタ５ａにレジスタ使用可能領域がない場合、第３割り当て部４ｆは、選択された仮想レジスタにおけるレジスタ生存区間のデータを格納するための実レジスタを予約する。
【００３７】
以上説明した本実施の形態に係るコンパイル装置４を用いることにより、キャッシュミスが発生しにくいレジスタ退避を実現することができ、レジスタ退避コストを改善できる。
【００３８】
また、本実施の形態においては、ＳＩＭＤ実レジスタ５ａの未使用領域をレジスタ退避領域として用いることによって、ＳＩＭＤ実レジスタ５ａを有効に使用することができる。
【００３９】
本実施の形態においては、コードシーケンスのクリティカルパスを減少させることができ、コードスケジューリングを改善できる。
【００４０】
そして、本実施の形態においては、コンパイル装置４の実行速度を早くすることができる。
【００４１】
なお、上記ステップＳ４においては、フラグＳの付された仮想レジスタにおけるレジスタ生存区間の重み値を高くし、フラグＳの付されていない仮想レジスタにおけるレジスタ生存区間の重み値を低くし、使用回数が少なく、区間の大きい仮想レジスタのレジスタ生存区間が、重み値を考慮して選択されるとしてもよい。
【００４２】
（第２の実施の形態）
本実施の形態においては、上記第１の実施の形態に係るコンパイル装置の詳細変形例について説明する。
【００４３】
図３は、本実施の形態に係る最適化コンパイル装置の構成の一例を示すブロック図である。
【００４４】
コンパイル装置８は、記憶装置２に記憶されており高級言語で書かれたソースプログラムコード６を入力する。記憶装置２としては、例えば主記憶装置又はディスク記憶装置などが用いられる。
【００４５】
コンパイル装置８の解析部９は、入力されたソースプログラムコード６に対する字句解析処理・構文解析処理等を行い、第１の中間コード１０を生成し、記憶装置２に記憶する。
【００４６】
字句解析処理では、入力されたソースプログラムコード６を形成している文字列が解析され、語句ごとに分割される。
【００４７】
例えば、構文解析処理では、字句解析処理によって得られた語句が上記高級言語の文法に照らして正しいか判断される。誤りがある場合、この誤りが通知され、実行が中止される。正しい場合、構文の解析結果である第１の中間コード１０が生成され、記憶装置２に記憶される。
【００４８】
最適化部１１は、第１の中間コード１０に対して処理を高速化するための最適化（生成されたオブジェクトプログラムがプロセッサで実行された場合の実行速度を高速化するための最適化）を行い、最適化された第２の中間コード１２を生成し、記憶装置２に記憶する。
【００４９】
なお、本実施の形態に係る最適化部１１において、命令スケジューリング部１３は、命令スケジューリングを行い、その後レジスタ割り当て部１４はレジスタ割り当てを行う。
【００５０】
より具体的には、例えば、最適化部１１は、フロー解析、データ依存解析、命令スケジューリング（命令割り当て）、レジスタ割り当て等を行う。
【００５１】
フロー解析処理では、第１の中間コード１０が生成された場合に、第１の中間コード１０に基づいて、プログラムの流れが解析される。
【００５２】
データ依存解析処理では、プログラムの流れが解析された後に、第１の中間コード１０を構成する各命令のデータ依存解析処理が実行され、依存グラフが生成され、例えば、どのような順番で命令割り当てが行われなければならないかといった制約が明らかにされる。
【００５３】
命令スケジューリング処理では、第１の中間コード１０に基づいて、オブジェクトプログラムの直前段階であり、仮想レジスタが割り当てられている第２の中間コード１２が生成される。
【００５４】
レジスタ割り当て処理では、命令スケジューリング処理によって生成された中間コードを、命令スケジューリングで仮に割り当てられていた仮想レジスタから、プロセッサの持つ実レジスタに、割り当てをし直す、というレジスタ割り当てが行われる。
【００５５】
本実施の形態においては、仮想レジスタと実レジスタとの対応がレジスタ対応表に登録されるとする。
【００５６】
出力部１５は、最適化された第２の中間コード１２に基づいて、プロセッサで実行可能な機械語コード７を生成し、記憶装置に２記憶する。すなわち、出力部１５は、上記レジスタ対応表に基づいて、最適化された第２の中間コード１２の仮想レジスタを実レジスタに置き換え、機械語コード７を出力する。
【００５７】
なお、第１及び第２の中間コード１０，１２は、通常、コンパイラ装置８内部で管理され、外部からはアクセスされない。
【００５８】
図４は、本実施の形態に係るコンパイル装置８のグラフカラーリング技法によるレジスタ割り当て処理の一例を示すフローチャートである。
【００５９】
ステップT１において、レジスタ割り当て部１４は、レジスタ干渉グラフを生成し、各ノードがスカラレジスタとして使用されているか、ＳＩＭＤレジスタとして使用されているか判断可能とするために、スカラレジスタとして使用されるノードに対してフラグＳを付す。
【００６０】
レジスタ干渉グラフにおけるノードは、仮想レジスタに対応する。仮想レジスタの値が定義されている点が別の仮想レジスタの生存区間内の場合、この仮想レジスタに対応するノードがエッジで結ばれる。
【００６１】
ステップT１においてレジスタ干渉グラフが生成された後、ステップＴ２〜Ｔ３においてレジスタ干渉グラフのどのノードから実レジスタを割り当てていくかが決定される。
【００６２】
ステップＴ２において、レジスタ割り当て部１４は、レジスタ干渉グラフ内の各ノードについて、ノードから出ているエッジの数（ノードに隣接している他のノードの数）が、割り当て可能な実レジスタの数よりも少ないノードを検出する。
【００６３】
隣接ノード数が割り当て可能な実レジスタの数より少ないノードが検出されない場合、ステップＴ３において、レジスタ割り当て部１４は、レジスタ退避候補のノードを選択し、処理はステップＴ４に移る。
【００６４】
このステップＴ３においてレジスタ退避候補のノードを選択する場合には、フラグSの付されているノードを優先的に選択する。また、レジスタ割り当て部は、フラグＳの付されているノードが複数存在する場合、この複数のフラグＳの付されているノードの間でヒューリスティックを用いて選択を行う。
【００６５】
なお、ヒューリスティックによってレジスタ退避候補のノードを選択する場合、フラグＳの付されているノードに所望の重みを与えて選択が行われるとしてもよい。この場合、仮にフラグＳが付されているノードが存在していたとしても、このフラグＳの付されているノードの重みよりもＳＩＭＤ使用タイプのノードの重みの方が大きい場合、ＳＩＭＤ使用タイプの仮想レジスタが選択される。
【００６６】
上記ステップＴ２においてノードが検出された場合又は上記ステップＴ３の後、ステップＴ４において、レジスタ割り当て部１４は、検出又は選択されたノードをレジスタ干渉グラフから削除してレジスタ干渉グラフを再構築する。ここで、レジスタ干渉グラフの再構築とは、検出又は選択されたノードと、この検出又は選択されたノードに接しているエッジをレジスタ干渉グラフから削除することを意味している。
【００６７】
ステップＴ５において、レジスタ割り当て部１４は、レジスタ干渉グラフ中のすべてのノードが削除されたか否か判断する。
【００６８】
レジスタ干渉グラフ中にノードが残っている場合、上記ステップＴ２に処理は戻り、レジスタ干渉グラフが空になるまで処理は繰り返される。
【００６９】
レジスタ干渉グラフのノードがすべて削除された場合、次に、実レジスタの割り当て処理が実行される。
【００７０】
ステップＴ６において、レジスタ割り当て部１４は、上記ステップＳ４によって削除された順序と逆の順序で、ノードを実レジスタに割り当てる。ここで、ノードに対して割り当てる実レジスタが見つからなかった場合には、このノードに対して割り当てを行わないまま、次以降のノードに対して実レジスタの割り当てが実行される。
【００７１】
ステップＴ７において、レジスタ割り当て部１４は、すべてのノードに対して、実レジスタが割り当てられたか否か判断する。
【００７２】
すべてのノードに対して、実レジスタが割り当てられている場合、レジスタ割り当て処理は終了する。
【００７３】
実レジスタが割り当てられていないノードが存在する場合、ステップＴ８において、レジスタ割り当て部１４は、実レジスタが割り当てられなかったノードに対して、メモリ（スタック領域）に格納・読み出しのためのレジスタ退避コードを挿入し、実レジスタが割り当てられていないノードのレジスタ生存区間を分割・短縮する。ステップＴ８実行後は、処理は上記ステップＴ１に戻る。
【００７４】
このステップＴ８において、フラグＳの付されているノードを退避させる場合、メモリに対するノードの退避・復帰コードを挿入する代わりに、退避用として確保された実レジスタの空いているスロットに対してデータを退避・復帰するためのレジスタ退避・復帰コードを挿入する。
【００７５】
また、退避用の実レジスタが確保されなかった場合、又は空スロットが十分な容量でない場合には、新たな退避用の実レジスタが確保される。そして、この確保された実レジスタは、上記ステップＴ２，Ｔ６において割り当て可能な実レジスタの候補から除外される。
【００７６】
上記各実施の形態は、上記の構成そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
【図面の簡単な説明】
【００７７】
【図１】本発明の第１の実施の形態に係るコンパイル装置の一例を示すブロック図。
【図２】第１の実施の形態に係るコンパイル装置によるレジスタ割り当てアルゴリズムの一例を示すフローチャート。
【図３】本発明の第２の実施の形態に係る最適化コンパイル装置の構成の一例を示すブロック図。
【図４】第２の実施の形態に係るコンパイル装置のグラフカラーリング技法によるレジスタ割り当て処理の一例を示すフローチャート。
【符号の説明】
【００７８】
１…プロセッサ、２…記憶装置、３…コンパイラ、４，８…コンパイル装置、４ａ…第１割り当て部、４ｂ…第１判断部、４ｃ…第２判断部、４ｄ…第２割り当て部、４ｅ…確保部、４ｆ…第３割り当て部、５…実レジスタ、５ａ…ＳＩＭＤ実レジスタ、５ｂ…スカラ実レジスタ、６…ソースプログラムコード、７…機械語コード、９…解析部、１０…第１の中間コード、１１…最適化部、１２…第２の中間コード、１３…命令スケジューリング部、１４…レジスタ割り当て部、１５…出力部
【図１】
2008009957.tif 000003
【図２】
2008009957.tif 000004
【図３】
2008009957.tif 000005
【図４】
2008009957.tif 000006