(57)【要約】【課題】プログラムの実行速度を向上させること。【解決手段】第１及び第２のスピル命令に第１のレジスタが割付けられている場合であって、各スピル命令の間の第１の区間に第１のレジスタが割付けられているときに、第１の区間における割付けの変更先の候補の第２のレジスタを探索する探索部３１と、第２のレジスタが割付けられた第２の区間と第１の区間とが重複していない場合には、第１の区間における割付けを第１のレジスタから第２のレジスタに変更し、第１及び第２の区間が重複している場合には、第２の区間における割付けを第２のレジスタから第３のレジスタに変更した後に、第１の区間における割付けを第１のレジスタから第２のレジスタに変更する変更部３２と、第１のスピル命令と第２のスピル命令のうち後に実行される命令を削除する削除部３３とを有するコンパイラ装置による。【選択図】図１３
2020135759.tif 000002
【特許請求の範囲】
【請求項１】
メモリ内の同一のデータを参照する第１のスピル命令と第２のスピル命令とを含む命令列を取得する取得部と、
前記第１のスピル命令と前記第２のスピル命令の各々に第１のレジスタが割付けられている場合であって、前記第１のスピル命令と前記第２のスピル命令との間の第１の区間に前記第１のレジスタが割付けられているときに、前記第１の区間における割付けの変更先の候補となる第２のレジスタを探索する探索部と、
前記命令列において前記第２のレジスタが割付けられた第２の区間と前記第１の区間とが重複していない場合には、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更し、前記第１の区間と前記第２の区間とが重複している場合には、前記第２の区間における割付けを前記第２のレジスタから第３のレジスタに変更した後に、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更する変更部と、
前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更した後に、前記第１のスピル命令と第２のスピル命令のうち、少なくとも後に実行される命令を削除する削除部と、
を有することを特徴とするコンパイラ装置。
【請求項２】
前記第１のスピル命令がスピルアウト命令であり、かつ前記第２のスピル命令が前記第１のスピル命令よりも後に実行されるスピルイン命令である場合には、前記削除部は、前記第１のスピル命令と前記第２のスピル命令の両方を削除することを特徴とする請求項１に記載のコンパイラ装置。
【請求項３】
前記第１のスピル命令と前記第２のスピル命令はスピルイン命令であることを特徴とする請求項１に記載のコンパイラ装置。
【請求項４】
前記命令列は基本ブロックの中にあり、
前記第２の区間が前記基本ブロックの最後まで延びている場合に、前記第２のスピル命令の後に、前記第３のレジスタの内容を前記第２のレジスタにコピーするコピー命令を追加する追加部を更に有することを特徴とする請求項１に記載のコンパイラ装置。
【請求項５】
メモリ内の同一のデータを参照する第１のスピル命令と第２のスピル命令とを含む命令列を取得する処理と、
前記第１のスピル命令と前記第２のスピル命令の各々に第１のレジスタが割付けられている場合であって、前記第１のスピル命令と前記第２のスピル命令との間の第１の区間に前記第１のレジスタが割付けられているときに、前記第１の区間における割付けの変更先の候補となる第２のレジスタを探索する処理と、
前記命令列において前記第２のレジスタが割付けられた第２の区間と前記第１の区間とが重複していない場合には、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更し、前記第１の区間と前記第２の区間とが重複している場合には、前記第２の区間における割付けを前記第２のレジスタから第３のレジスタに変更した後に、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更する処理と、
前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更した後に、前記第１のスピル命令と第２のスピル命令のうち、少なくとも後に実行される命令を削除する処理と、
をコンピュータに実行させるためのプログラム。
【請求項６】
メモリ内の同一のデータを参照する第１のスピル命令と第２のスピル命令とを含む命令列を取得する処理と、
前記第１のスピル命令と前記第２のスピル命令の各々に第１のレジスタが割付けられている場合であって、前記第１のスピル命令と前記第２のスピル命令との間の第１の区間に前記第１のレジスタが割付けられているときに、前記第１の区間における割付けの変更先の候補となる第２のレジスタを探索する処理と、
前記命令列において前記第２のレジスタが割付けられた第２の区間と前記第１の区間とが重複していない場合には、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更し、前記第１の区間と前記第２の区間とが重複している場合には、前記第２の区間における割付けを前記第２のレジスタから第３のレジスタに変更した後に、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更する処理と、
前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更した後に、前記第１のスピル命令と第２のスピル命令のうち、少なくとも後に実行される命令を削除する処理と、
をコンピュータが実行することを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラ装置、プログラム、及び情報処理方法に関する。
【背景技術】
【０００２】
プログラムの実行速度を向上させるためのコンパイラの最適化技法の一つにレジスタ割付けがある。レジスタ割付けは、メモリのデータをレジスタに予め転送しておくことにより、プログラムの実行時におけるメモリアクセスを減らす技法である。メモリアクセスよりもレジスタアクセスの方が速いため、このようにレジスタ割付けを行うことでプログラムの実行速度を向上させることができる。
【０００３】
但し、レジスタの個数は限られているため、レジスタに格納しきれないデータについては、スピルアウト命令によってレジスタからメモリに追い出す必要がある。また、メモリに追い出されたデータが必要となった場合には、そのデータを再びレジスタに転送するスピルイン命令を実行する必要がある。スピルアウト命令やスピルイン命令等のスピル命令は、それぞれstore命令やload命令等のメモリ参照命令であるためメモリアクセスに長時間を要し、プログラムの実行速度を低下させてしまう。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１０７８１６号公報
【特許文献２】特開２００２−３１２１７９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一側面によれば、本発明は、プログラムの実行速度を向上させることを目的とする。
【課題を解決するための手段】
【０００６】
一側面によれば、メモリ内の同一のデータを参照する第１のスピル命令と第２のスピル命令とを含む命令列を取得する取得部と、前記第１のスピル命令と前記第２のスピル命令の各々に第１のレジスタが割付けられている場合であって、前記第１のスピル命令と前記第２のスピル命令との間の第１の区間に前記第１のレジスタが割付けられているときに、前記第１の区間における割付けの変更先の候補となる第２のレジスタを探索する探索部と、前記命令列において前記第２のレジスタが割付けられた第２の区間と前記第１の区間とが重複していない場合には、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更し、前記第１の区間と前記第２の区間とが重複している場合には、前記第２の区間における割付けを前記第２のレジスタから第３のレジスタに変更した後に、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更する変更部と、前記第１の区間における割付けを前記第１のレジスタから前記第２のレジスタに変更した後に、前記第１のスピル命令と第２のスピル命令のうち、少なくとも後に実行される命令を削除する削除部とを有するコンパイラ装置が提供される。
【発明の効果】
【０００７】
一側面によれば、プログラムの実行速度を向上させることができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、本実施形態に係るターゲットマシンのハードウェア構成図である。
【図２】図２は、本実施形態において、基本ブロックにおける命令とレジスタの割付けとを模式的に示す図である。
【図３】図３は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その１）である。
【図４】図４は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その２）である。
【図５】図５は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その３）である。
【図６】図６は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その４）である。
【図７】図７は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その５）である。
【図８】図８は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その１）である。
【図９】図９は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その２）である。
【図１０】図１０は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その３）である。
【図１１】図１１は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その４）である。
【図１２】図１２は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その５）である。
【図１３】図１３は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その６）である。
【図１４】図１４は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その７）である。
【図１５】図１５は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その８）である。
【図１６】図１６は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その９）である。
【図１７】図１７は、本実施形態の第２例におけるコピー命令と後続の基本ブロックとの関係の一例について示す図である。
【図１８】図１８は、本実施形態の第３例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その１）である。
【図１９】図１９は、本実施形態の第３例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その２）である。
【図２０】図２０は、本実施形態の第３例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その３）である。
【図２１】図２１は、本実施形態の第３例に係るレジスタ割付けの変更方法の概略について模式的に示す図（その４）である。
【図２２】図２２は、本実施形態に係るコンパイラ装置のハードウェア構成図である。
【図２３】図２３は、本実施形態に係るコンパイラ装置の機能について示す機能構成図である。
【図２４】本実施形態に係る情報処理方法について示すフローチャートである。
【図２５】図２５は、本実施形態に係るレジスタ割付けの変更処理について示すフローチャート（その１）である。
【図２６】図２６は、本実施形態に係るレジスタ割付けの変更処理について示すフローチャート（その２）である。
【発明を実施するための形態】
【０００９】
（本実施形態）
図１は、本実施形態に係るターゲットマシンのハードウェア構成図である。
【００１０】
このターゲットマシン１は、サーバやPC(Personal Computer)等の計算機であって、プロセッサ２とメモリ３とを有する。
【００１１】
このうち、プロセッサ２は、算術演算や論理演算を行うALU(Arithmetic and Logic Unit)等の演算部４とレジスタファイル５とを備える。レジスタファイル５は、複数のレジスタを備えたデバイスであって、この例では各レジスタに１番、２番、…と順番に番号を付す。
【００１２】
一方、メモリ３は、各種のプログラムが展開されるDRAM(Dynamic Random Access Memory)等の揮発性メモリである。
【００１３】
このようなターゲットマシン１でプログラムを実行する場合には、メモリ３におけるデータをスピルイン命令で予めレジスタファイル５に転送しておくことでプログラムの実行速度が向上する。また、プログラムの実行中には、スピルアウト命令によってレジスタファイル５からメモリ３にデータが追い出されることがある。
【００１４】
このターゲットマシン１で実行される命令列は、コンパイラがソースコードをコンパイルすることにより出力される。
【００１５】
図２は、そのコンパイラによって出力された基本ブロック１０における命令とレジスタの割付けとを模式的に示す図である。なお、基本ブロック１０は、分岐命令以外の命令を実行順に並べた命令列であり、０番から１４番の順に命令が実行される。
【００１６】
また、レジスタについては、上から下に向かってレジスタ番号が増えるように並べている。そして、命令に割付け済みのレジスタには斜線やドットのハッチングを掛けてある。なお、ここでは、命令に割付け済みのレジスタは、命令が用いるデータを割付け済みのレジスタのことを指す。また、スピル命令によって転送されるデータを割付けたレジスタに斜線のハッチングを掛け、スピル命令によらないデータを割付けたレジスタにドットのハッチングを掛けてある。また、命令が用いるデータに割り付けられていない空きレジスタは白抜きにしてある。
【００１７】
この例では、１番命令、８番命令、及び１１番命令がスピルイン命令となっている。スピルイン命令によってレジスタに転送されるデータはメモリ３内のスタック領域で管理される。スタック領域の各データにはスタック番号が割り当てられており、そのスタック番号で各データを一意に識別できる。上記の各スピルイン命令は、いずれもスタック番号が２７のデータを２番レジスタに転送するload命令である。
【００１８】
メモリアクセスを減らすにはなるべくスピルイン命令を減らすのが好ましい。しかし、この例では、１番のスピルイン命令が実行された後に３番命令と６番命令の各々に２番レジスタが割付けられており、これらの命令によって２番レジスタの内容が書き換えられる可能性がある。よって、３番命令と６番命令の実行が終了した後に、再び８番のスピルイン命令を実行する必要がある。また、コンパイラの最適化が不十分であるため、その後の１１番のスピルイン命令が不必要に命令列に含まれてしまっている。
【００１９】
プログラムの実行速度を速めるには、８番と１１番のスピルイン命令を削除すればよい。そのためには、３番命令と６番命令におけるレジスタの割付け先を２番レジスタから他のレジスタに変更し、区間[２、７]及び区間[９、１０]において２番レジスタを割付けないようにすればよい。なお、区間[２、１０]は、２番命令から１０番命令までの区間である。同様に、以下ではi番命令からj番命令までの区間を[i、j]で表す。
そのようなレジスタ割付けの変更方法について次に説明する。
【００２０】
レジスタ割付けの変更は、変更先のレジスタが空いているか否かに応じて異なる方法で行われる。そこで、まず、変更先のレジスタが空いている場合の第１例に係る変更方法について説明する。
【００２１】
・第１例
図３〜図７は、本実施形態の第１例に係るレジスタ割付けの変更方法の概略について模式的に示す図である。
【００２２】
以下では、図２のようにレジスタが割付けられている場合を例にして説明する。
【００２３】
まず、図３に示すように、区間[３、３]における２番レジスタの割付けの変更先の候補となるレジスタを探索する。この例では、区間[３、３]において１１番レジスタが空いているため、区間[３、３]における２番レジスタの割付けの変更先の候補を１１番レジスタとする。なお、以下では、レジスタ割付けの変更元や変更先のレジスタを太い黒枠で示す。
【００２４】
次に、図４に示すように、区間[３、３]におけるレジスタの割付けを２番レジスタから１１番レジスタに変更する。
【００２５】
そして、上記と同様の探索を区間[６、６]に割付けられた２番レジスタについても行う。区間[６、６]で空いているレジスタは６番レジスタであるため、この例では区間[６、６]における２番レジスタ割付けの変更先の候補を６番レジスタとする。
【００２６】
次いで、図５に示すように、区間[６、６]におけるレジスタの割付けを２番レジスタから６番レジスタに変更する。
【００２７】
これにより、図６に示すように、１番のスピルイン命令に割付けられた２番レジスタのデータが書き換えられずに保持される保持区間を１１番命令まで延ばすことができる。よって、８番のスピルイン命令を削除しても、１番のスピルイン命令によって２番レジスタに格納されたデータは１１番命令まで変更を受けなくなる。
【００２８】
そこで、図７に示すように、不要な８番のスピルイン命令を削除する。また、コンパイラの不十分な最適化により追加されていた１１番のスピルイン命令もここで削除する。
【００２９】
これにより、メモリアクセスが必要なスピルイン命令が一つのみになり、かつ基本ブロック１０における命令列も短くなるため、プログラムの実行速度を向上させることができる。なお、図７では、１番のスピルイン命令に割付けられたデータが保持される区間に斜線のハッチングをかけてある。
【００３０】
以上説明したように、二つのスピル命令の間の区間にこれらのスピル命令が使用するのと同じレジスタが割付けられている場合に、その区間で他のレジスタが空いているときには、これらのレジスタ間で割付けを変更できる。これにより、二つのスピル命令のうちで後に実行される方を削除してもプログラムの実行結果は変わらず、当該スピル命令を削除してプログラムの実行速度を向上させることが可能となる。
【００３１】
但し、変更先のレジスタが割付けられている区間と、変更元のレジスタが割付けられている区間とが重複している場合には、上記の方法では割付けの変更を行うことができない。そこで、次に、各レジスタが割付けられている区間が重複している場合におけるレジスタ割付けの変更方法について説明する。
【００３２】
・第２例
図８〜図１６は、本実施形態の第２例に係るレジスタ割付けの変更方法の概略について模式的に示す図である。
【００３３】
図８の例では、図３の例と同様に、１番、８番、及び１１番の各命令が、メモリ３上でスタック番号が２７のデータを２番レジスタに転送するスピルイン命令となっている。但し、区間[３、６]に２番レジスタが割付けられており、２番レジスタが割付けられている区間が図３のそれよりも長くなっている。
【００３４】
この場合は、区間[３、６]の始点で空いているレジスタを探索する。この例では区間[３、６]の始点で１１番レジスタが空いているため、その１１番レジスタを２番レジスタの割付けの変更先の候補とする。
【００３５】
但し、１１番レジスタが割付けられている区間は[４、１４]であり、２番レジスタが割付けられている区間[３、６]と重複しているため、区間[３、６]における割付けを２番レジスタから１１番レジスタに変更することができない。
【００３６】
そこで、図９に示すように、区間[４、１４]における割付けを１１番レジスタから他のレジスタに変更するため、その変更先の候補を探索する。ここでは、区間[４、１４]の始点で空いている１０番レジスタを変更先の候補とする。
【００３７】
但し、１０番レジスタが割付けられている区間は[５、６]であり、１１番レジスタが割付けられている区間[４、１４]と重複しているため、区間[４、１４]における割付けを１１番レジスタから１０番レジスタに変更することができない。
【００３８】
そのため、図１０に示すように、今度は区間[５、６]における割付けを１０番レジスタから他のレジスタに変更するため、その変更先の候補を探索する。ここでは、上記と同様に区間[５、６]の始点で空いている９番レジスタを変更先の候補とする。
【００３９】
しかし、９番レジスタが割付けられている区間は[６、７]であり、１０番レジスタが割付けられている区間[５、６]と重複しているため、区間[５、６]における割付けを１０番レジスタから９番レジスタに変更することができない。
【００４０】
そこで、更に図１１に示すように、区間[６、７]における割付けを９番レジスタから他のレジスタに変更するために、その変更先の候補を探索する。上記と同様に、ここでも区間[６、７]の始点で空いている６番レジスタを変更先の候補とする。
【００４１】
但し、６番レジスタが割付けられている区間は[７、７]であり、９番レジスタが割付けられている区間[６、７]と重複しているため、区間[６、７]における割付けを９番レジスタから６番レジスタに変更することができない。
【００４２】
よって、更に図１２に示すように区間[７、７]における割付け先を６番レジスタから他のレジスタに変更するために、その変更先の候補を探索する。ここでは、初めにレジスタ割付けの変更先の探索を行った２番レジスタを除いて、区間[７、７]の始点で空いている５番レジスタを変更先の候補とする。
【００４３】
今度は、区間[７、７]の全区間において５番レジスタが空いているため、区間[７、７]における割付けを６番レジスタから５番レジスタに変更することが可能となる。
【００４４】
そこで、図１３に示すように、区間[７、７]における割付けを６番レジスタから５番レジスタに変更する（ステップＰ１）。これにより区間[６、７]の全区間において６番レジスタが空き、区間[６、７]における割付けを９番レジスタから６番レジスタに変更する（ステップＰ２）。この結果、更に区間[５、６]の全区間において９番レジスタが空き、区間[５、６]における割付けを１０番レジスタから９番レジスタに変更する（ステップＰ３）。
【００４５】
同様に、区間[４、１４]における割付けを１１番レジスタから１０番レジスタに変更し（ステップＰ４）、最後に区間[３、６]における割付けを２番レジスタから１１番レジスタに変更する（ステップＰ５）。
【００４６】
以上により、図１４に示すように、１番のスピルイン命令で２番レジスタに転送されたデータが書き換えられずに保持される保持区間が[１、１１]となり、その区間内に８番と１１番のスピルイン命令が入るようになる。よって、第１例と同様に８番と１１番のスピルイン命令を削除でき、プログラムの実行速度を向上することができる。
【００４７】
なお、この例では、レジスタ割付けの変更によって１１番レジスタの内容が１０番レジスタに移っており、この状態が基本ブロック１０の最後の１４番命令まで継続する。複数の基本ブロックは、各々の最初と最後の命令間でレジスタの割付けを統一することで、プログラムの実行結果の正確性が担保される。例えば、基本ブロックの最後の命令に割付けられたレジスタが後続の基本ブロックの最初の命令にも割付けられていないと、本来使用すべきデータとは異なるデータを利用して後続の基本ブロックが実行されてしまう。
【００４８】
これを避けるため、この例では、図１５に示すように、基本ブロック１０の最後の１５番命令としてコピー命令を追加する。そのコピー命令は、１０番レジスタの内容を１１番レジスタにコピーする命令である。
【００４９】
なお、コピー命令を追加する位置は特に限定されず、コピー先の１１番レジスタが割付られていない区間にコピー命令を追加し得る。例えば、６番命令の後にコピー命令を追加することができる。
【００５０】
その後に、図１６に示すように、８番と１１番の不要なスピルイン命令を削除する。この状態では、基本ブロック１０の最後に前述のコピー命令が追加されている。なお、図１６では、１番のスピルイン命令に割付けられたデータが保持される区間に斜線のハッチングをかけてある。
【００５１】
図１７は、そのコピー命令と後続の基本ブロック１１との関係の一例について示す図である。
【００５２】
図１７に示すように、コピー命令を追加したことにより、基本ブロック１０の最後の１３番命令と、基本ブロック１１の最初の１番命令のそれぞれのレジスタ割付けが一致する。これにより、レジスタ割付けを変更する前と同じレジスタの内容を基本ブロック１１の１番命令が使用できるようになり、基本ブロック１１の実行結果をレジスタ割付けの変更前と同一にすることができる。
【００５３】
以上説明した例では、図１６のように二つのスピルイン命令を削除することで基本ブロック１０に含まれる命令数が減り、ターゲットマシン１におけるプログラムの実行速度が向上する。しかも、メモリアクセスを要するスピルイン命令を削除したことでプログラムの実行速度を更に向上することができる。
【００５４】
・第３例
前述の第１例と第２例ではスピルイン命令を削除したが、同様の手順でスピルアウト命令も削除することができる。これについて以下に説明する。
【００５５】
図１８〜図２１は、本実施形態の第３例に係るレジスタ割付けの変更方法の概略について模式的に示す図である。
【００５６】
図１８の例では、０番命令が、０番レジスタの内容をメモリ３に転送するスピルアウト命令となっている。なお、転送先は、メモリ３でスタック番号が１０の領域である。また、７番命令は、スタック番号が１０のデータを０番レジスタに転送するスピルイン命令である。
【００５７】
この場合は、区間[３、５]において０番レジスタが割付けられており、その区間[３、５]で０番レジスタの内容が書き換えられないように０番命令でスピルアウトを行い、０番レジスタのデータをメモリ３に退避させている。そして、区間[３、５]の各命令が終了した後に７番命令でスピルインをすることにより、メモリ３に退避させたデータを再び０番レジスタに転送している。
【００５８】
よって、０番のスピルアウト命令と７番のスピルイン命令を削除するには、第１例や第２例と同じ手順でレジスタ割付けを変更することにより、区間[３、５]から０番レジスタの割付けを外せばよい。
【００５９】
この例では、図１９のステップＰ１〜Ｐ６の順にレジスタ割付けを変更する。
【００６０】
これにより、図２０に示すように、０番のスピルアウト命令と７番のスピルイン命令との間の区間[１、６]において０番レジスタの割付けが外される。よって、区間[１、６]において０番レジスタの内容が変更されなくなるため、０番のスピルアウト命令で０番レジスタのデータをメモリ３に退避させる必要がなくなる。更に、このように退避させたデータを０番レジスタに戻すための７番のスピルイン命令も不要となる。
【００６１】
そこで、図２１に示すように、これらのスピルアウト命令とスピルイン命令とを削除する。これにより、前述の第１例や第２例と同様にプログラムの実行速度を向上することができる。なお、図２１では、新たに使用中となり得るレジスタに斜線のハッチングをかけてある。
【００６２】
＜ハードウェア構成＞
次に、前述の第１例〜第３例のようにレジスタ割付けを変更できるコンパイラ装置について説明する。
【００６３】
図２２は、本実施形態に係るコンパイラ装置のハードウェア構成図である。
【００６４】
このコンパイラ装置２１は、コンパイルプログラムを実行するPCやサーバ等の計算機であり、記憶部２２、メモリ２３、プロセッサ２４、入力部２５、及び表示部２６を備える。これらの各部はバス２７によって相互に接続される。
【００６５】
このうち、記憶部２２は、例えばHDD(Hard Disk Drive)やSSD(Solid State Drive)等の二次記憶装置であり、本実施形態に係るコンパイルプログラム２９を記憶する。コンパイルプログラム２９は、入力された命令列におけるレジスタ割付けを変更し、変更後の命令列を出力するコンパイラである。
【００６６】
なお、そのコンパイルプログラム２９をコンピュータが読み取り可能な記録媒体２８に記録させておき、プロセッサ２４に記録媒体２８のコンパイルプログラム２９を読み取らせるようにしてもよい。
【００６７】
そのような記録媒体２８としては、例えばCD-ROM(Compact Disc - Read Only Memory)、DVD(Digital Versatile Disc)、及びUSB(Universal Serial Bus)メモリ等の物理的な可搬型記録媒体がある。また、フラッシュメモリ等の半導体メモリやハードディスクドライブを記録媒体２８として使用してもよい。これらの記録媒体２８は、物理的な形態を持たない搬送波のような一時的な媒体ではない。
【００６８】
更に、公衆回線、インターネット、及びLAN(Local Area Network)等に接続された装置にコンパイルプログラム２９を記憶させておき、プロセッサ２４がコンパイルプログラム２９を読み出して実行するようにしてもよい。
【００６９】
一方、メモリ２３は、DRAM等のようにデータを一時的に記憶するハードウェアであって、その上に前述のコンパイルプログラム２９が展開される。
【００７０】
プロセッサ２４は、自装置の各部を制御したり、メモリ２３と協働してコンパイルプログラム２９を実行したりするCPU(Central Processing Unit)等のハードウェアである。
【００７１】
入力部２５は、キーボードやマウス等の入力デバイスである。ユーザがこれらの入力デバイスを操作することにより、コンパイルプログラム２９の入力先や出力先等が指定される。
【００７２】
また、表示部２６は、コンパイルプログラム２９の実行時にユーザが使用する様々なコマンドを表示する液晶ディスプレイ等の表示デバイスである。なお、以下ではコンパイラ装置２１がコンパイルプログラム２９を実行する場合を例にして説明するが、ターゲットマシン１（図１参照）がコンパイルプログラム２９を実行することにより以下の各処理や機能を実現してもよい。
【００７３】
＜機能構成＞
次に、このコンパイラ装置２１の機能構成について説明する。
図２３は、本実施形態に係るコンパイラ装置２１の機能について示す機能構成図である。
【００７４】
コンパイラ装置２１は、命令列の入力を受け付けてその中の不要なスピル命令を削除する装置であって、取得部３０、探索部３１、変更部３２、削除部３３、及び追加部３４を備える。これらの各部は、プロセッサ２４とメモリ２３が協働して前述のコンパイルプログラム２９を実行することにより実現される。
【００７５】
このうち、取得部３０は、他のコンパイラが生成した命令列を取得する機能ユニットである。
【００７６】
また、探索部３１は、図３や図８に示したように、取得した命令列におけるレジスタ割付けを変更するために、そのレジスタ割付けの変更先の候補となるレジスタを探索する機能ユニットである。
【００７７】
例えば、図３のように１番のスピルイン命令と１１番のスピルイン命令の各々に２番レジスタが割付けられており、これらの命令間の３番命令に２番レジスタが割付けられている場合を考える。この場合は、探索部３１が、区間[３、３]における２番レジスタの割付けの変更先の候補を探索する。その候補は、前述のように区間[３、３]の始点で空いている１１番レジスタとなる。
【００７８】
また、図８の例では、探索部３１は、区間[３、６]における２番レジスタの割付けの変更先の候補を探索する。この場合の候補も、区間[３、６]の始点で空いている１１番レジスタとなる。
探索部３１がレジスタ割付けの変更先の候補となるレジスタを探索する際には、初めにどのレジスタの割付けを変更する目的なのかを考慮して行われる。例えば、図１２では、初めは区間[２、７]および区間[９、１０]において２番レジスタを割当てないように変更することが目的である。図１２の例では、探索部３１は、区間[７、７]における６番レジスタの割付けの変更先の候補を探索する。この場合の候補は、初めに区間[２、７]における２番レジスタの割付けを変更する目的であるため、２番レジスタを除いて、区間[７、７]の始点で空いている５番レジスタとする。
【００７９】
一方、変更部３２は、レジスタ割付けの変更を行う機能ユニットである。割付けをどのように変更するかは各レジスタが割付けられた区間を考慮して行われる。
【００８０】
例えば、図３のように、割付けの変更元の２番レジスタが区間[３、３]に割付けられており、割付けの変更先の候補の１１番レジスタが区間[５、１４]に割付けられている場合を考える。このように各区間[３、３]、[５、１４]が重複していない場合には、区間[３、３]における割付けを２番レジスタから１１番レジスタに変更する。
【００８１】
一方、図８のように、割付けの変更元の２番レジスタが区間[３、６]に割付けられており、これと重複する区間[４、１４]に割付けられた１１番レジスタが割付けの変更先の候補である場合を考える。この場合は、変更部３２は、図１３に示したように、ステップＰ１〜Ｐ４を実行することにより区間[４、１４]における割付けを１１番レジスタから１０番レジスタに変更する。その後のステップＰ５において、変更部３２は、区間[３、６]における割付けを２番レジスタから１１番レジスタに変更する。
【００８２】
また、削除部３３は、変更部３２がレジスタ割付けを変更した後に不要なスピル命令を削除する。図６の例では、２番のスピルイン命令と１１番のスピルイン命令のうち、後に実行される１１番のスピルイン命令は不要となるため、削除部３３は１１番のスピルイン命令を削除する。また、２番と１１番の間の８番のスピルイン命令も不要であるため、削除部３３は８番のスピルイン命令も削除する。これについては図１５の例でも同様である。
【００８３】
一方、図２０の例のように最初に０番のスピルアウト命令が実行され、その後に７番のスピルイン命令が実行される場合には、前述のようにこれらのスピル命令の両方を削除できる。そこで、この場合は、削除部３３は、スピルアウト命令とスピルイン命令の両方を削除する。
【００８４】
また、追加部３４は、図１３〜図１５に示したように、基本ブロック１０の最後にコピー命令を追加する機能ユニットである。図１３の例では、２番レジスタの割付け変更先である１１番レジスタが区間[４、１４]に割付けられており、基本ブロック１０の最後まで延びている。この場合には、プログラムの実行結果がレジスタ割付けの変更前と変わらないようにするために、追加部３４は、図１５に示したように、１０番レジスタの内容を１１番レジスタにコピーするコピー命令を追加する。
【００８５】
＜フローチャート＞
次に、本実施形態に係る情報処理方法について説明する。
図２４は、本実施形態に係る情報処理方法について示すフローチャートである。
【００８６】
まず、ステップＳ１において、取得部３０が、他のコンパイラが生成した命令列を取得する。
【００８７】
次に、ステップＳ２に移り、取得した命令列の中で不要なスピル命令の候補を探索部３１が探索する。基本ブロック１０に複数のスピル命令が存在する場合は、メモリ３内の同一のスタック番号のデータを参照しており、かつ同一のレジスタが割付けられているスピル命令が不要なスピル命令の候補となる。例えば、図３と図８の例では、１番、８番、１１番の各スピルイン命令が不要なスピル命令の候補となる。また、図１８の例では、０番のスピルアウト命令と７番のスピルイン命令が不要なスピル命令の候補となる。
【００８８】
なお、スピル命令とそれ以外の命令との弁別や、各命令に割付けられたレジスタ番号の取得等は、命令列を生成した他のコンパイラが出力するログ情報等に基づいて探索部３１が行い得る。
【００８９】
次に、ステップＳ３に移り、削除対象のスピル命令を探索部３１が選択する。
【００９０】
ステップＳ２で不要と判断されたスピル命令の全てがスピルイン命令の場合には、その中で最初に実行されるスピルイン命令を除いた後続の全てのスピルイン命令が削除対象となる。例えば、図３と図８の例では、８番と１１番の各スピルイン命令が削除対象のスピル命令として選択される。
【００９１】
また、ステップＳ２においてスピルイン命令と後続のスピルアウト命令とが不要と判断された場合には、これらスピルイン命令とスピルアウト命令の両方が削除対象となる。例えば、図１８の例では、０番のスピルアウト命令と７番のスピルイン命令の両方が削除対象として選択される。
【００９２】
次に、ステップＳ４に移り、変更部３２がレジスタ割付けの変更処理を行う。その変更処理の詳細については後述する。
【００９３】
次に、ステップＳ５に移り、追加部３４が、キューにコピー命令があるかどうかを判断する。キューは、図１５で説明したコピー命令をキューイングするためのデータ構造であって、追加部３４がメモリ３の中に作成する。そのコピー命令は、基本ブロックの最後まで延びている区間におけるレジスタの割付けを変更した場合にキューに追加される。
【００９４】
ここで、キューにコピー命令がある（ＹＥＳ）と判断された場合にはステップＳ６に移る。
【００９５】
ステップＳ６においては、追加部３４がキューの先頭のコピー命令を基本ブロックの最後に追加し、レジスタ割付けの変更前と比べてプログラムの実行結果が変わらないようにする。その後に後述のステップＳ７に移る。
【００９６】
一方、ステップＳ５においてキューにコピー命令がない（ＮＯ）と判断された場合にはステップＳ７に移り、削除部３３が不要なスピル命令を削除する。
【００９７】
図３と図８の例では、削除部３３は、８番と１１番の各スピルイン命令を削除する。また、図１８の例では、削除部３３は、０番のスピルアウト命令と７番のスピルイン命令を削除する。
【００９８】
以上により、本実施形態に係る情報処理方法の基本ステップを終了する。この後は、上記のようにスピル命令を削除した命令列を他のコンパイラに入力し、そのコンパイラがターゲットマシン１（図１参照）で実行可能なオブジェクトファイルを生成する。
【００９９】
次に、ステップＳ４のレジスタ割付けの変更処理について詳細に説明する。
【０１００】
図２５及び図２６は、本実施形態に係るレジスタ割付けの変更処理について示すフローチャートである。
【０１０１】
このレジスタ割付けの変更処理は、関数func(in_range, regA, rangeN, regN)を再帰的に呼び出すことで実現される。関数funcの引数のうち、in_rangeは区間を表す変数である。また、regAは、A番目のレジスタを表す変数である。そして、range Nはレジスタ割付けの変更の対象外とする区間の集合であり、regNはレジスタ割付けの変更の対象外とするレジスタである。なお、関数funcを最初に呼び出すときには、in_rangeとrangeNとを同じに設定し、regAとregNとを同じに設定する。
【０１０２】
なお、以下では、ステップＳ３における削除対象のスピル命令を除いた区間in_range内でレジスタreg Aがデータを保持する区間の集合をrange Aで表す。
【０１０３】
例えば、in_range = [１、１０]の場合には、range A = {[１、１]、[２、５]、[７、８]}等のように表される。また、集合range Aの要素をrange Xとも書く。この例では、range X = [１、１]、range X = [２、５]、range X = [７、８]となる。
【０１０４】
関数func(in_range, regA, rangeN, regN)の呼び出しに先立ち、探索部３１は、in_range、reg A、rangeN、regNのそれぞれの初期値をセットする。このうち、in_rangeは、ステップＳ１で探索した不要なスピル命令の候補のうち、最初のスピル命令から最後のスピル命令までの区間である。また、rangeN及びregNは、関数func(in_range, regA, rangeN, regN)を初めて呼び出すときに、それぞれin_range及びregAと同じ値にセットされる。例えば、図３と図８の例では、in_range = [１、１１]、rangeN＝[１、１１]となる。また、図１８の例では、in_range = [０、７]、rangeN＝[０、７]となる。なお、これらの区間は、図３や図８の命令列を生成した他のコンパイラが出力するログに基づいて探索部３１が特定することができる。
【０１０５】
また、reg Aは、ステップＳ３の削除対象の各スピル命令がメモリ参照の際に使用するレジスタである。図３と図８の例では、メモリ３のデータの転送先である２番レジスタがreg Aとなる。そして、図１８の例では、０番のスピルアウト命令によるデータの転送元のレジスタであり、かつ７番のスピルイン命令によるデータの転送先のレジスタである０番レジスタがreg Aとなる。
【０１０６】
このように初期化をした後の関数funcの処理内容について説明する。
【０１０７】
まず、ステップＳ１１において、探索部３１が、区間in_range内でレジスタreg Aがデータを保持する区間の集合range Aを探索する。例えば、図８の例では、in_range = [１、１１]であり、reg Aは２番レジスタであり、range A = {[３、６]}となる。
【０１０８】
次に、ステップＳ１２に移り、探索部３１が、集合range Aの要素があるかどうかを判断する。ここで、集合range Aの要素はない（ＮＯ）と判断された場合には、区間in_range内でレジスタreg Aはデータを保持しておらず、区間in_range内でレジスタreg Aが割付けられた命令は存在しないということになる。このような状態では、図１４のように、８番のスピルイン命令を除いて区間[１、１１]内で２番レジスタが割付けられた命令が存在しないため、レジスタ割付けを変更しなくても、不要な８番と１１番のスピルイン命令を削除できる。
よって、この場合はレジスタ割付けを行わずに、処理に成功したものとして終了する。
【０１０９】
一方、ステップＳ１２において集合range Aの要素はある（ＹＥＳ）と判断された場合には、区間in_range内でレジスタreg Aが割付けられた命令が存在することになる。例えば、図８の例では前述のようにrange A = {[３、６]}となるため、集合range Aの要素はある（ＹＥＳ）と判断される。この場合にはレジスタ割付けの変更が必要となるため、次のステップＳ１３に移る。
【０１１０】
ステップＳ１３では、探索部３１が、ステップＳ１１で探索した集合range Aの要素である各区間のうち、始点が最も早い区間range Xを特定する。そして、その区間range Xの始点において空いているレジスタreg Bを探索する。この探索は、区間の集合rangeNにおけるレジスタregNを除いて行う。すなわち、区間rangeXの始点が区間rangeNに含まれ、かつ、レジスタregNがレジスタregBと一致するということがないようにレジスタregBを探索する。そのレジスタreg Bは、区間range Xにおけるレジスタreg Aの割付けの変更先の候補となる。
【０１１１】
図８の例では、range A = {[３、６]}であるから、range X = [３、６]となる。そして、range X = [３、６]の始点である３番命令で空いている１１番レジスタがreg Bになる。なお、図１２の例では、rangeX=[７、７]の始点である７番命令で空いているレジスタとして２番レジスタがある。しかし、７番命令はrangeN=[１、１１]に含まれ、かつregN=２であるため、2番レジスタは選ばれない。
【０１１２】
次に、ステップＳ１４に移り、探索部３１が、レジスタreg Bが見つかったかどうかを判断する。ここで、見つからない（ＮＯ）と判断された場合には、レジスタreg Aの割付けをレジスタreg Bに変更することができない。よって、この場合には、レジスタ割付けの変更が失敗して処理を終える。
【０１１３】
一方、ステップＳ１４において見つかった（ＹＥＳ）と判断された場合にはステップＳ１５に移る。
【０１１４】
ステップＳ１５では、探索部３１が、区間range X内でレジスタreg Bがデータを保持する区間の集合range Bを探索する。
【０１１５】
図８の例では、range X = [３、６]であり、かつレジスタreg Bは１１番レジスタである。よって、range B = {[４、１４]}となる。
【０１１６】
次に、ステップＳ１６に移り、探索部３１が、集合range Bの要素があるかどうかを判断する。ここで、集合range Bの要素はある（ＹＥＳ）と判断された場合には、このままでは区間range Xにおけるレジスタ割付けをレジスタreg Aからレジスタreg Bに変更することができない。例えば、図８の例では、区間[３、６]におけるレジスタ割付けを２番レジスタから１１番レジスタに変更することはできない。
【０１１７】
よって、この場合にはステップＳ１７に移り、探索部３１が、集合range Bの中で始点が最も早い区間range Yを特定する。そして、探索部３１が関数func(rangeY, regB, rangeN, regN)を呼び出す再帰呼び出しを行う。
【０１１８】
例えば、図８の例ではrange B = {[４、１４]}であるから、range Y＝[４、１４]となる。
【０１１９】
その後、ステップＳ１８に移り、再帰呼び出しの結果が成功したかどうかを探索部３１が判断し、成功した（ＹＥＳ）と判断された場合にはステップＳ１１からやり直す。また、成功しなかった（ＮＯ）と判断された場合には、レジスタ割付けの変更に失敗して処理を終える。
【０１２０】
一方、前述のステップＳ１６において集合range Bの要素はない（ＮＯ）と判断された場合には、区間range_X内でレジスタreg Bが割付けられた命令は存在しないということになる。例えば、図１２の例では、range_X＝[７、７]であり、regBは５番レジスタとなっているため、range B＝{}となり、区間[７、７]内で５番レジスタが割付けられた命令は存在しない。
【０１２１】
よって、この場合にはステップＳ１９に移り、変更部３２が、区間range_Xにおけるレジスタ割付けをレジスタreg Aからレジスタreg Bに変更する。例えば、図１３の例でrange_X＝[７、７]であり、reg Aが６番レジスタであり、reg Bが５番レジスタである場合には、区間[７、７]におけるレジスタ割付けを６番レジスタから５番レジスタに変更する。
【０１２２】
次に、ステップＳ２０に移り、追加部３４が、区間range_Xが基本ブロックの最後まで延びているかどうかを判断する。例えば、図１３の例でrange_X＝[４、１４]の場合には、区間range_Xが基本ブロックの最後まで延びていると判断される。
【０１２３】
このように延びている（ＹＥＳ）と判断された場合には、ステップＳ２１に移り、追加部３４が、レジスタreg Bの内容をレジスタreg Aにコピーするコピー命令をメモリ３内のキューに追加する。例えば、前述の図１３の例でrange_X＝[４、１４]であり、reg Aが１１番レジスタであり、reg Bが１０番レジスタである場合には、１０番レジスタの内容を１１番レジスタにコピーするコピー命令をキューに追加する。
【０１２４】
なお、ステップＳ２０において延びていない（ＮＯ）と判断された場合にはキューにコピー命令を追加することなく処理を終える。
以上により、本実施形態に係るレジスタ割付けの変更処理の基本ステップを終了する。
【０１２５】
上記した本実施形態によれば、図２４のステップＳ４でレジスタ割付けの変更処理を行うことで、各スピル命令の間の区間でレジスタの空きを作ることができ、ステップＳ７で不要なスピル命令を削除することができる。これにより、プログラムに含まれる命令数を低減できると共に、プログラム実行時のメモリアクセスの回数が減るため、プログラムの実行速度を向上させることができる。
【０１２６】
以上、本実施形態について詳細に説明したが、本実施形態は上記に限定されない。例えば、図２５及び図２６では関数funcの再帰呼び出しによりレジスタ割付けの変更処理を行ったが、関数の再帰呼び出しを行わずに、ループ処理によりレジスタ割付けの変更処理を行ってもよい。
【符号の説明】
【０１２７】
１…ターゲットマシン、２…プロセッサ、３…メモリ、４…演算部、５…レジスタファイル、２１…コンパイラ装置、２２…記憶部、２３…メモリ、２４…プロセッサ、２５…入力部、２６…表示部、２７…バス、２８…記録媒体、３０…取得部、３１…探索部、３２…変更部、３３…削除部、３４…追加部。
【図１】
2020135759.tif 000003
【図２】
2020135759.tif 000004
【図３】
2020135759.tif 000005
【図４】
2020135759.tif 000006
【図５】
2020135759.tif 000007
【図６】
2020135759.tif 000008
【図７】
2020135759.tif 000009
【図８】
2020135759.tif 000010
【図９】
2020135759.tif 000011
【図１０】
2020135759.tif 000012
【図１１】
2020135759.tif 000013
【図１２】
2020135759.tif 000014
【図１３】
2020135759.tif 000015
【図１４】
2020135759.tif 000016
【図１５】
2020135759.tif 000017
【図１６】
2020135759.tif 000018
【図１７】
2020135759.tif 000019
【図１８】
2020135759.tif 000020
【図１９】
2020135759.tif 000021
【図２０】
2020135759.tif 000022
【図２１】
2020135759.tif 000023
【図２２】
2020135759.tif 000024
【図２３】
2020135759.tif 000025
【図２４】
2020135759.tif 000026
【図２５】
2020135759.tif 000027
【図２６】
2020135759.tif 000028