(57)【特許請求の範囲】
【請求項１】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、
他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを探し出すリーフセクション判定段階と、
前記リーフセクション内の参照ラベルを参照する分岐命令を有するセクションを探し出す参照セクション判定段階と、
前記リーフセクションと該リーフセクション内の参照ラベルを参照する分岐命令を有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、
前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階と
を具備することを特徴とする最適化方法。
【請求項２】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、
他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出すメインセクション判定段階と、
前記メインセクション内の分岐命令が参照する参照ラベルを有するセクションを探し出す被参照セクション判定段階と、
前記メインセクションと該メインセクション内の分岐命令が参照する参照ラベルを有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、
前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階と
を具備することを特徴とする最適化方法。
【請求項３】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、
他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを１つ探し出す第２段階と、
第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有するセクションを１つ探し出す第３段階と、
第２段階で探し出されたリーフセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、
第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなリーフセクションとする第５段階と、
第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、
第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなリーフセクションとする第７段階と、
第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有する他のセクションを１つ探し出す第８段階と、
より短いコードに置換できるコードに変換された分岐命令を有するセクションが見つかるまで、または、全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、
第５段階および第７段階で生成された新たなリーフセクションも含めた全てのリーフセクションに対して第２段階から第９段階までの処理が行われるまで、第２段階から第９段階までの処理を繰り返す第１０段階と、
第２段階から第１０段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１１段階と、
第１１段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１２段階と
を具備することを特徴とする最適化方法。
【請求項４】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、
他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出す第２段階と、
第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有するセクションを１つ探し出す第３段階と、
第２段階で探し出されたメインセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、
第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなメインセクションとする第５段階と、
第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、
第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなメインセクションとする第７段階と、
第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有する他のセクションを１つ探し出す第８段階と、
全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、
第２段階から第９段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１０段階と、
第１０段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１１段階と
を具備することを特徴とする最適化方法。
【請求項５】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法をコンピュータに実行させるためのプログラムを記録した記録媒体であって、
前記コンピュータに、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、
他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを探し出すリーフセクション判定段階と、
前記リーフセクション内の参照ラベルを参照する分岐命令を有するセクションを探し出す参照セクション判定段階と、
前記リーフセクションと該リーフセクション内の参照ラベルを参照する分岐命令を有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、
前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階と
を実行させるためのプログラムを記録した記録媒体。
【請求項６】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法をコンピュータに実行させるためのプログラムを記録した記録媒体であって、
前記コンピュータに、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、
他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出すメインセクション判定段階と、
前記メインセクション内の分岐命令が参照する参照ラベルを有するセクションを探し出す被参照セクション判定段階と、
前記メインセクションと該メインセクション内の分岐命令が参照する参照ラベルを有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、
前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階と
を実行させるためのプログラムを記録した記録媒体。
【請求項７】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法をコンピュータに実行させるためのプログラムを記録した記録媒体であって、
前記コンピュータに、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、
他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを１つ探し出す第２段階と、
第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有するセクションを１つ探し出す第３段階と、
第２段階で探し出されたリーフセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、
第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなリーフセクションとする第５段階と、
第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、
第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなリーフセクションとする第７段階と、
第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有する他のセクションを１つ探し出す第８段階と、
より短いコードに置換できるコードに変換された分岐命令を有するセクションが見つかるまで、または、全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、第５段階および第７段階で生成された新たなリーフセクションも含めた全てのリーフセクションに対して第２段階から第９段階までの処理が行われるまで、第２段階から第９段階までの処理を繰り返す第１０段階と、
第２段階から第１０段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１１段階と、
第１１段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１２段階と
を実行させるためのプログラムを記録した記録媒体。
【請求項８】
参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法をコンピュータに実行させるためのプログラムを記録した記録媒体であって、
前記コンピュータに、
複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、
他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出す第２段階と、
第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有するセクションを１つ探し出す第３段階と、
第２段階で探し出されたメインセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、
第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなメインセクションとする第５段階と、
第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、
第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなメインセクションとする第７段階と、
第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有する他のセクションを１つ探し出す第８段階と、
全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、
第２段階から第９段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１０段階と、
第１０段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１１段階と
を実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分岐命令の最適化方法およびそのプログラムを記録した記録媒体に関し、より詳細には、飛び先として参照される参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する、分岐命令の最適化方法およびそのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
一般的に、アセンブリ言語のプログラムは、モジュール単位で記述され、モジュールは１つ又は複数のセクションから構成される。
そして、該プログラムは、アセンブラによって、セクション単位で、機械語（以下、「コード」と称する）に変換される、即ち、アセンブルされる。
その後、セクション間およびモジュール間は、リンカによって結合される、即ち、リンクされる。
【０００３】
このような一連の処理において、プログラム中の分岐命令は、アセンブル時に、分岐命令と参照ラベルとの距離に応じて、コード長が異なる２種類以上のコードのいずれかに変換される。
一例として、上記距離が２５５バイト以下ならば、参照アドレス部が８ビットであるショートコードに変換され、上記距離が２５５バイトより大きければ、参照アドレス部が２０ビットであるロングコードに変換される。
【０００４】
但し、プログラムは上述したようにセクション単位でアセンブルされるので、ある分岐命令の参照ラベルが該分岐命令とは別のセクション内に存在する場合、このような分岐命令（以下、「セクション間分岐命令」と称する）と参照ラベルとの距離をアセンブル時に知ることはできない。
故に、従来の方法では、たとえ上記距離が所定値（上記一例では、２５５バイト）以下であるとしても、セクション間分岐命令は、全て、ロングコードに変換されていた。
その結果、プログラム全体のサイズが不要に大きくなってしまうという課題があった。
【０００５】
上記課題を解決するために発明されたのが、特開昭６２−２０５４３１号公報（以下、「第１公報」と称する）記載の発明である。
第１公報には、アセンブル時には、分岐命令を全て一時的にロングコードに変換しておき、リンク時に、分岐命令とその参照ラベルとの距離を実際に計算することによって、上記距離が所定値以下であるセクション間分岐命令をロングコードからショートコードに置換する方法が開示されている。
【０００６】
しかしながら、第１公報の発明は、「ショートコードに置換できるか否か」をプログラム全体にわたって、一度しか検証しないので、該検証において明らかにショートコードに変換できる分岐命令しか置換しない。
そのため、第１公報の発明は、あるロングコードがショートコードに置換された影響によって他の分岐命令と参照ラベルとの距離が所定値（上記一例では、２５５バイト）以下になったとしても、該他の分岐命令が変換されたロングコードをショートコードに置換することができない。
【０００７】
即ち、例えば、ある分岐命令と参照ラベルとの間に存在する分岐命令が多数ショートコードに置換されたために、該ある分岐命令と参照ラベルとの距離が上記所定値以下になったとしても、第１公報の発明では、該ある分岐命令自体がショートコードに置換されることはない。
その結果、第１公報の発明には、依然として、「プログラム全体のサイズが不要に大きくなってしまう」という課題があった。
【０００８】
上記課題を解決するために発明されたのが、特開平８−２４１１９６号公報（以下、「第２公報」と称する）記載の発明である。
第２公報には、あるロングコードがショートコードに置換された場合、該置換による影響を、他の分岐命令が変換されたロングコードのセクション内オフセットや参照ラベルのセクション内オフセットやセクションサイズなどにフィードバックすることによって、より大きな最適化効果を得る方法が開示されている。
【０００９】
【発明が解決しようとする課題】
しかしながら、第２公報の発明は、最初に与えられたセクションの結合順番で結合された場合だけしか「ショートコードに置換できるか否か」を検証しないので、該検証においてショートコードに変換できる分岐命令しか置換しない。
そのため、第２公報の発明は、ロングコードがあるセクションの先頭近くにあり、参照ラベルが該セクションの後ろに結合された別のセクションの終端近くにある場合、このようなロングコードをショートコードに置換することができない。
その結果、第２公報の発明には、依然として、「プログラム全体のサイズが不要に大きくなってしまう」という課題があった。
【００１０】
また、第１公報の発明および第２公報の発明は、共に、セクション間分岐命令にしか着目していない。
そのため、第１公報の発明および第２公報の発明は、あるロングコードがショートコードに置換された影響によって他のセクション内分岐命令と参照ラベルとの距離が所定値以下になったとしても、該他のセクション内分岐命令が変換されたロングコードをショートコードに置換することができない。
その結果、第１公報の発明および第２公報の発明には、依然として、「プログラム全体のサイズが不要に大きくなってしまう」という課題があった。
【００１１】
本発明は、このような背景の下になされたもので、（上記第１公報の発明および第２公報の発明を含めた）従来の方法と比較して、プログラム全体のサイズをより最適化できる分岐命令の最適化方法およびその記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
請求項１記載の発明は、参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを探し出すリーフセクション判定段階と、前記リーフセクション内の参照ラベルを参照する分岐命令を有するセクションを探し出す参照セクション判定段階と、前記リーフセクションと該リーフセクション内の参照ラベルを参照する分岐命令を有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階とを具備することを特徴とする。
請求項２記載の発明は、参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する初期情報準備段階と、他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出すメインセクション判定段階と、前記メインセクション内の分岐命令が参照する参照ラベルを有するセクションを探し出す被参照セクション判定段階と、前記メインセクションと該メインセクション内の分岐命令が参照する参照ラベルを有するセクションとをいずれかの順番で隣接結合することによって、前記分岐命令が変換されたコードをより短いコードに置換できるならば、該置換および該隣接結合を実行する置換可能性判定段階と、前記置換可能性判定段階の処理の結果によるプログラム全体のサイズが前記初期情報準備段階で保存されたサイズ以上ならば、セクションの結合順番を前記初期情報準備段階で結合された順番に戻す最適化判定段階とを具備することを特徴とする。
請求項３記載の発明は、参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、他のセクション内の参照ラベルを参照する分岐命令を有しないセクションであるリーフセクションを１つ探し出す第２段階と、第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有するセクションを１つ探し出す第３段階と、第２段階で探し出されたリーフセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなリーフセクションとする第５段階と、第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなリーフセクションとする第７段階と、第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたリーフセクション内の参照ラベルを参照する分岐命令を有する他のセクションを１つ探し出す第８段階と、より短いコードに置換できるコードに変換された分岐命令を有するセクションが見つかるまで、または、全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、第５段階および第７段階で生成された新たなリーフセクションも含めた全てのリーフセクションに対して第２段階から第９段階までの処理が行われるまで、第２段階から第９段階までの処理を繰り返す第１０段階と、第２段階から第１０段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１１段階と、第１１段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１２段階とを具備することを特徴とする。
請求項４記載の発明は、参照ラベルまでの距離に応じてコード長が異なる２種類以上のコードのいずれかに変換される分岐命令を、前記距離に基づいてより短いコードへ最適化する最適化方法において、複数のセクションを入力された順番で結合し、その状態で各セクション内の分岐命令を最適化し、プログラム全体のサイズを保存する第１段階と、他のセクション内の参照ラベルを参照する分岐命令を最も多く有するセクションであるメインセクションを探し出す第２段階と、第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有するセクションを１つ探し出す第３段階と、第２段階で探し出されたメインセクションと第３段階で探し出されたセクションとを隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第４段階と、第４段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第４段階で隣接結合された順番で１つの新たなメインセクションとする第５段階と、第４段階の判断の結果、より短いコードに置換できないならば、前記２つのセクションの順番を入れ替えて隣接結合し、前記分岐命令が変換されたコードをより短いコードに置換できるか否かを判断する第６段階と、第６段階の判断の結果、より短いコードに置換できるならば、該置換を実行すると共に、前記２つのセクションを第６段階で隣接結合された順番で１つの新たなメインセクションとする第７段階と、第６段階の判断の結果、より短いコードに置換できないならば、第２段階で探し出されたメインセクション内の分岐命令が参照する参照ラベルを有する他のセクションを１つ探し出す第８段階と、全てのセクションに対して第４段階および第６段階の判断が行われるまで、第３段階から第８段階までの処理を繰り返す第９段階と、第２段階から第９段階までの処理の結果によるプログラム全体のサイズが第１段階で保存されたサイズよりも小さいか否かを判断する第１０段階と、第１０段階の判断の結果、第１段階で保存されたサイズ以上ならば、セクションの結合順番を第１段階で結合された順番に戻す第１１段階とを具備することを特徴とする。
請求項５記載の発明は、請求項１記載の各段階をコンピュータに実行させるためのプログラムを記録した記録媒体である。
請求項６記載の発明は、請求項２記載の各段階をコンピュータに実行させるためのプログラムを記録した記録媒体である。
請求項７記載の発明は、請求項３記載の各段階をコンピュータに実行させるためのプログラムを記録した記録媒体である。
請求項８記載の発明は、請求項４記載の各段階をコンピュータに実行させるためのプログラムを記録した記録媒体である。
【００１３】
【発明の実施の形態】
§１．基本的概念
本発明の基本的概念を以下に説明する。
本発明は、セクションのリンク時における結合順番を変更することによって、セクション間分岐命令のコードをより短いコードに変換する。
図１は、本発明の基本的概念を示す説明図である。
この図において、分岐命令“ｊｍｐ  ｌａｂｅｌ”  は、セクションＳＥＣ１の先頭近くにあり、参照ラベル“ｌａｂｅｌ”  は、セクションＳＥＣ２の終端近くにあるとする。
【００１４】
従来の方法では、図１（ａ）に示されるように、これらのセクションがＳＥＣ１，ＳＥＣ２の順番でリンカに入力されると、これらのセクションを入力された順番で結合し、最適化を試みる。
そのため、従来の方法では、図１（ａ）に示されるように、分岐命令“ｊｍｐ  ｌａｂｅｌ”  と参照ラベル“ｌａｂｅｌ”  との距離が大きいので、分岐命令“ｊｍｐ  ｌａｂｅｌ”  はロングコードに変換されてしまう。
【００１５】
一方、本発明では、図１（ｂ）に示されるように、セクションを入力された順番以外の順番でも結合し、最適化を試みる。
そのため、本発明では、図１（ｂ）に示されるように、分岐命令“ｊｍｐ  ｌａｂｅｌ”  と参照ラベル“ｌａｂｅｌ”  との距離が小さくなり、分岐命令“ｊｍｐ  ｌａｂｅｌ”  はより短いコード（ショートコード）に変換される。
【００１６】
§２．第１実施形態
以下、図面を参照して、この発明の第１実施形態について説明する。
本実施形態による最適化方法は、ＣＰＵ（中央処理装置）およびその周辺回路からなるコンピュータ装置で実行可能である。
該コンピュータ装置は、所定の記録媒体（磁気ディスク、半導体メモリ等）に記録された制御プログラムで制御されることによって、本実施形態による最適化方法を実行する。
また、上記制御プログラムは通信回線を介して頒布することが可能である。
【００１７】
次に、本実施形態による最適化方法の処理内容を説明する。
第１実施形態による最適化方法は、セクション間分岐命令を有しないセクションであるリーフセクション内の参照ラベルを参照する分岐命令を有するセクションを該リーフセクションに順次隣接結合していきながら分岐命令の最適化を行う。
【００１８】
図２は、この発明の第１実施形態による最適化方法の一例を示すフローチャートである。
アセンブルされたセクションの結合（即ち、リンク）をオペレータが指示すると、本方法の処理はステップ２１０１へ進む。なお、この時点では、各セクション内の分岐命令が変換されたコードは、全てロングコードである。
【００１９】
ステップ２１０１では、セクションを一時的な順番として、入力された順番で結合し、リロケーション情報テーブルと参照ラベル情報テーブルとセクション結合順番情報とセクション情報テーブルとを生成する。
【００２０】
ここで、リロケーション情報テーブルは、各分岐命令について、少なくとも、以下の２種類の情報を保持する。
（１）分岐命令のセクション内オフセット
（２）分岐命令が参照する参照ラベル名
【００２１】
参照ラベル情報テーブルは、各参照ラベルについて、少なくとも、以下の３種類の情報を保持する。
（１）参照ラベル名
（２）参照ラベルのセクション内オフセット
（３）参照ラベルが存在するセクション名
セクション結合順番情報は、セクションの結合順番をセクション名または、セクションＩＤで保持する。
【００２２】
セクション情報テーブルは、各セクションについて、少なくとも、以下の５種類の情報を保持する。
（１）セクション名およびセクションＩＤ
（２）セクションのサイズ
（３）セクション内に存在するセクション間分岐命令の数
（４）処理済みフラグ（後述するステップ２１１０参照）
（５）結合情報（後述するステップ２１０９参照）
【００２３】
また、本実施形態では、上記リロケーション情報テーブルと参照ラベル情報テーブルとセクション結合順番情報とセクション情報テーブルとの他に、リーフセクション参照情報テーブルを使用する。
リーフセクション参照情報テーブルは、着目リーフセクション内に存在する参照ラベルを参照するロングコードを有するセクションのセクション情報を保持する。
ここで、「着目リーフセクション」とは、現在処理中のリーフセクションを指す。また、「リーフセクション」とは、他のセクション内の参照ラベルを参照する分岐命令（セクション間分岐命令）を有しないセクションを指す。
但し、「リーフセクション」と他のセクションとを結合して新たなリーフセクションとした場合にはこの限りではなく、セクション間分岐命令を有する場合もある。
【００２４】
ステップ２１０１の後、ステップ２１０２へ進む。
ステップ２１０２では、ステップ２１０１の順番で結合されたセクションに対して、上記第１公報の発明および第２公報の発明を含めた従来の方法による最適化を行い、該最適化の結果によるプログラム全体のサイズを保存する。
その後、ステップ２１０３へ進む。
【００２５】
ステップ２１０３では、各セクション内に存在するセクション間分岐命令の数をカウントし、該カウント値をセクション情報テーブルに格納する。
その後、ステップ２１０４へ進む。
【００２６】
ステップ２１０４では、セクション情報テーブルから以下のステップ２２０１を経ていないセクション情報を１つ読み出す。
その後、ステップ２２０１へ進む。
【００２７】
ステップ２２０１では、ステップ２１０４で読み出されたセクション情報に対応するセクションがリーフセクションであるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ２１０４で読み出されたセクション情報に対応するセクションがリーフセクションでないならば）、ステップ２２０２へ進む。
【００２８】
ステップ２２０２では、ステップ２１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ２１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報でないならば）、ステップ２１０４へ戻る。
【００２９】
一方、ステップ２２０１の判断結果が「ＹＥＳ」である場合（即ち、ステップ２１０４で読み出されたセクション情報に対応するセクションがリーフセクションであるならば）、または、ステップ２２０２の判断結果が「ＹＥＳ」である場合（即ち、ステップ２１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるならば）、ステップ２１０４’へ進む。なお、以下、ステップ２２０１で検出された上記リーフセクションを「着目リーフセクション」と称する。
【００３０】
ステップ２１０４’では、セクション情報テーブルから以下のステップ２２０３を経ていないセクション情報を１つ読み出す。
その後、ステップ２２０３へ進む。
【００３１】
ステップ２２０３では、ステップ２１０４’で読み出されたセクション情報に対応するセクションが着目リーフセクション内の参照ラベルを参照するロングコードを有するか否かを判断する。
この判断結果が「ＹＥＳ」である場合（即ち、ステップ２１０４’で読み出されたセクション情報に対応するセクションが着目リーフセクション内の参照ラベルを参照するロングコードを有するならば）、ステップ２１０５へ進む。
【００３２】
ステップ２１０５では、ステップ２１０４’で読み出されたセクション情報をリーフセクション参照情報テーブルに格納する。
その後、ステップ２２０２’へ進む。
また、ステップ２２０３の判断結果が「ＮＯ」である場合も（即ち、ステップ２１０４’で読み出されたセクション情報に対応するセクションが着目リーフセクション内の参照ラベルを参照するロングコードを有しないならば）、ステップ２２０２’へ進む。
【００３３】
ステップ２２０２’では、ステップ２１０４’で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるか否かを判断する。この判断結果が「ＮＯ」である場合（即ち、ステップ２１０４’で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報でないならば）、ステップ２１０４’へ戻る。
【００３４】
一方、ステップ２２０２’の判断結果が「ＹＥＳ」である場合（即ち、ステップ２１０４’で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるならば）、ステップ２１０６へ進む。
【００３５】
ステップ２１０６では、リーフセクション参照情報テーブルからセクション情報を１つ読み出す。なお、以下、このセクション情報に対応するセクションを「着目セクション」と称する。
その後、ステップ２１０７へ進む。
【００３６】
ステップ２１０７では、着目セクションと着目リーフセクションとを隣接結合した場合について、着目セクション内のロングコードと着目リーフセクション内の（該ロングコードが参照する）参照ラベルとの距離を計算する。
その後、ステップ２２０４へ進む。
【００３７】
ステップ２２０４では、ステップ２１０７で計算された距離に基づいて、着目セクション内の上記ロングコードをショートコードへ置換できるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、着目セクション内の上記ロングコードをショートコードへ置換できないならば）、ステップ２１０８へ進む。
【００３８】
ステップ２１０８では、着目セクションと着目リーフセクションとの順番を入れ替えて隣接結合した場合について、着目セクション内のロングコードと着目リーフセクション内の（該ロングコードが参照する）参照ラベルとの距離を計算する。
その後、ステップ２２０４’へ進む。
【００３９】
ステップ２２０４’では、ステップ２１０８で計算された距離に基づいて、着目セクション内の上記ロングコードをショートコードへ置換できるか否かを判断する。
ここで、ステップ２２０４またはステップ２２０４’の判断結果が「ＹＥＳ」である場合（即ち、着目セクション内の上記ロングコードをショートコードへ置換できるならば）、ステップ２１０９へ進む。
【００４０】
ステップ２１０９では、着目セクション内の上記ロングコードをショートコードへ置換する。
また、着目セクションと着目リーフセクションとを隣接結合することを決定し、該結合情報をセクション情報テーブルに格納する。
以降、両セクションの隣接結合によって生成されたセクションは、１つのリーフセクションとしてみなされる。
なお、このときの結合順番は、ステップ２２０４の判断結果が「ＹＥＳ」の場合には、ステップ２１０７で仮定された順番であり、一方、ステップ２２０４’の判断結果が「ＹＥＳ」の場合には、ステップ２１０８で仮定された順番であるとする。
また、置換された上記ロングコードと同じセクション内に存在しかつ該ロングコードよりも後に存在する分岐命令および参照ラベルについて、リロケーション情報テーブルのセクション内オフセットと参照ラベル情報テーブルのセクション内オフセットとを更新する。
その後、ステップ２１１０へ進む。
【００４１】
一方、ステップ２２０４’の判断結果が「ＮＯ」である場合（即ち、着目セクション内の上記ロングコードをショートコードへ置換できないならば）、ステップ２２０５へ進む。
【００４２】
ステップ２２０５では、ステップ２１０６で読み出されたセクション情報がリーフセクション参照情報テーブル内の最後のセクション情報であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ２１０６で読み出されたセクション情報がリーフセクション参照情報テーブル内の最後のセクション情報でないならば）、ステップ２１０６へ戻る。
【００４３】
一方、ステップ２２０５の判断結果が「ＹＥＳ」である場合（即ち、ステップ２１０６で読み出されたセクション情報がリーフセクション参照情報テーブル内の最後のセクション情報であるならば）、ステップ２１１０へ進む。
【００４４】
ステップ２１１０では、ステップ２１０４で読み出されたセクション情報の処理済みフラグを“１”に更新する。
その後、ステップ２２０６へ進む。
【００４５】
ステップ２２０６では、セクション情報テーブルの全てのセクション情報の処理済みフラグが“１”であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、処理済みフラグが“０”であるセクション情報が１つでもあるならば）、ステップ２１０４へ戻る。
一方、ステップ２２０６の判断結果が「ＹＥＳ」である場合（即ち、全てのセクション情報の処理済みフラグが“１”であるならば）、ステップ２２０７へ進む。
【００４６】
ステップ２２０７では、ステップ２１０４〜２２０６の処理の結果によるプログラム全体のサイズがステップ２１０２で保存されたサイズよりも小さいか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ２１０４〜２２０６の処理の結果によるプログラム全体のサイズがステップ２１０２で保存されたサイズ以上であるならば）、ステップ２１１１へ進む。
【００４７】
ステップ２１１１では、セクションの結合順番を初期状態（ステップ２１０１で結合された順番）に戻す。
その後、ステップ２１１２へ進む。
一方、ステップ２２０７の判断結果が「ＹＥＳ」である場合も（即ち、ステップ２１０４〜２２０６の処理の結果によるプログラム全体のサイズがステップ２１０２で保存されたサイズよりも小さいならば）、ステップ２１１２へ進む。
【００４８】
ステップ２１１２では、分岐命令と参照ラベルとの距離を計算して、処理を終了する。
以上で、第１実施形態の説明を終了する。
【００４９】
§３．第２実施形態
以下、図面を参照して、この発明の第２実施形態について説明する。
第２実施形態による最適化方法も、ＣＰＵ（中央処理装置）およびその周辺回路からなるコンピュータ装置で実行可能である。
該コンピュータ装置は、所定の記録媒体（磁気ディスク、半導体メモリ等）に記録された制御プログラムで制御されることによって、本実施形態による最適化方法を実行する。
また、上記制御プログラムは通信回線を介して頒布することが可能である。
【００５０】
次に、本実施形態による最適化方法の処理内容を説明する。
第２実施形態による最適化方法は、セクション間分岐命令を最も多く有するセクションであるメインセクション内の分岐命令が参照する参照ラベルを有するセクションを該メインセクションに順次隣接結合していきながら分岐命令の最適化を行う。
【００５１】
図３は、この発明の第２実施形態による最適化方法の一例を示すフローチャートである。
アセンブルされたセクションの結合をオペレータが指示すると、本方法の処理はステップ３１０１へ進む。
ステップ３１０１〜３１０３の処理は、第１実施形態のステップ２１０１〜２１０３の処理と同じものである。
【００５２】
但し、本実施形態では、（第１実施形態の）リーフセクション参照情報テーブルの代わりに、メインセクション情報およびメインセクション参照情報テーブルを使用する。
メインセクション情報は、セクション間分岐命令を最も多く有するセクション即ち、メインセクションのセクション情報を保持し、メインセクション参照情報テーブルは、メインセクション内に存在するロングコードが参照する参照ラベルを有するセクションのセクション情報を保持する。
【００５３】
ステップ３１０３の後、ステップ３１０４へ進む。
ステップ３１０４では、セクション情報テーブルから以下のステップ３２０１を経ていないセクション情報を１つ読み出す。
その後、ステップ３２０１へ進む。
【００５４】
ステップ３２０１では、ステップ３１０４で読み出されたセクション情報のセクション間分岐命令数がこれまでに読み出されたセクション情報のセクション間分岐命令数よりも大きいか否かを判断する。なお、上記「これまでに読み出されたセクション間分岐命令数」は、本方法の開始時に、初期値として０に設定される。
この判断結果が「ＹＥＳ」の場合（即ち、ステップ３１０４で読み出されたセクション情報のセクション間分岐命令数がこれまでに読み出されたセクション間分岐命令数よりも大きいならば）、ステップ３１０５へ進む。
【００５５】
ステップ３１０５では、ステップ３１０４で読み出されたセクション情報をメインセクション情報に格納する。
その後、ステップ３２０２へ進む。
一方、ステップ３２０１の判断結果が「ＮＯ」の場合も（即ち、ステップ３１０４で読み出されたセクション情報のセクション間分岐命令数がこれまでに読み出されたセクション間分岐命令数以下であるならば）、ステップ３２０２へ進む。
【００５６】
ステップ３２０２では、ステップ３１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ３１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報でないならば）、ステップ３１０４へ戻る。
【００５７】
一方、ステップ３２０２の判断結果が「ＹＥＳ」である場合（即ち、ステップ３１０４で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるならば）、ステップ３１０６へ進む。
【００５８】
ステップ３１０６では、セクション情報テーブルから以下のステップ３２０３を経ていないセクション情報を１つ読み出す。
その後、ステップ３２０３へ進む。
【００５９】
ステップ３２０３では、ステップ３１０６で読み出されたセクション情報に対応するセクション内の参照ラベルを参照するロングコードをメインセクションが有するか否かを判断する。
この判断結果が「ＹＥＳ」である場合（即ち、ステップ３１０６で読み出されたセクション情報に対応するセクション内の参照ラベルを参照するロングコードをメインセクションが有するならば）、ステップ３１０７へ進む。
【００６０】
ステップ３１０７では、ステップ３１０６で読み出されたセクション情報をメインセクション参照情報テーブルに格納する。
その後、ステップ３２０２’へ進む。
一方、ステップ３２０３の判断結果が「ＮＯ」である場合も（即ち、ステップ３１０６で読み出されたセクション情報に対応するセクション内の参照ラベルを参照するロングコードをメインセクションが有しないならば）、ステップ３２０２’へ進む。
【００６１】
ステップ３２０２’では、ステップ３１０６で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ３１０６で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報でないならば）、ステップ３１０６へ戻る。
【００６２】
一方、ステップ３２０２’の判断結果が「ＹＥＳ」である場合（即ち、ステップ３１０６で読み出されたセクション情報がセクション情報テーブル内の最後のセクション情報であるならば）、ステップ３１０８へ進む。
【００６３】
ステップ３１０８では、メインセクション参照情報テーブルから以下のステップ３１０９を経ていないセクション情報を１つ読み出す。なお、以下、このセクション情報に対応するセクションを「着目セクション」と称する。
その後、ステップ３１０９へ進む。
【００６４】
ステップ３１０９では、メインセクションと着目セクションとを隣接結合した場合について、メインセクション内のロングコードと着目セクション内の（該ロングコードが参照する）参照ラベルとの距離を計算する。
その後、ステップ３２０４へ進む。
【００６５】
ステップ３２０４では、ステップ３１０７で計算された距離に基づいて、メインセクション内の上記ロングコードをショートコードへ置換できるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、メインセクション内の上記ロングコードをショートコードへ置換できないならば）、ステップ３１１０へ進む。
【００６６】
ステップ３１１０では、メインセクションと着目セクションとの順番を入れ替えて隣接結合した場合について、メインセクション内のロングコードと着目セクション内の（該ロングコードが参照する）参照ラベルとの距離を計算する。
その後、ステップ３２０４’へ進む。
【００６７】
ステップ３２０４’では、ステップ３１１０で計算された距離に基づいて、メインセクション内の上記ロングコードをショートコードへ置換できるか否かを判断する。
ここで、ステップ３２０４またはステップ３２０４’の判断結果が「ＹＥＳ」である場合（即ち、メインセクション内の上記ロングコードをショートコードへ置換できるならば）、ステップ３１１１へ進む。
【００６８】
ステップ３１１１では、メインセクション内の上記ロングコードをショートコードへ置換する。
また、メインセクションと着目セクションとを隣接結合することを決定し、該結合情報をセクション情報テーブルに格納する。
以降、両セクションの隣接結合によって生成されたセクションは、１つのメインセクションとしてみなされる。
なお、このときの結合順番は、ステップ３２０４の判断結果が「ＹＥＳ」の場合には、ステップ３１０７で仮定された順番であり、一方、ステップ３２０４’の判断結果が「ＹＥＳ」の場合には、ステップ３１０８で仮定された順番であるとする。
また、置換された上記ロングコードと同じセクション内に存在しかつ該ロングコードよりも後に存在する分岐命令および参照ラベルについて、リロケーション情報テーブルのセクション内オフセットと参照ラベル情報テーブルのセクション内オフセットとを更新する。
その後、ステップ３１１２へ進む。
一方、ステップ３２０４’の判断結果が「ＮＯ」である場合も（即ち、メインセクション内の上記ロングコードをショートコードへ置換できないならば）、ステップ３１１２へ進む。
【００６９】
ステップ３１１２では、ステップ３１０８で読み出されたセクション情報の処理済みフラグを“１”に更新する。
その後、ステップ３２０５へ進む。
【００７０】
ステップ３２０５では、セクション情報テーブルの全てのセクション情報の処理済みフラグが“１”であるか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、処理済みフラグが“０”であるセクション情報が１つでもあるならば）、ステップ３１０８へ戻る。
【００７１】
一方、ステップ３２０６の判断結果が「ＹＥＳ」である場合（即ち、全てのセクション情報の処理済みフラグが“１”であるならば）、ステップ３２０６へ進む。
【００７２】
ステップ３２０６では、ステップ３１０４〜３２０５の処理の結果によるプログラム全体のサイズがステップ３１０２で保存されたサイズよりも小さいか否かを判断する。
この判断結果が「ＮＯ」である場合（即ち、ステップ３１０４〜３２０５の処理の結果によるプログラム全体のサイズがステップ３１０２で保存されたサイズ以上であるならば）、ステップ３１１３へ進む。
【００７３】
ステップ３１１３では、セクションの結合順番を初期状態（ステップ３１０１で結合された順番）に戻す。
その後、ステップ３１１４へ進む。
一方、ステップ３２０６の判断結果が「ＹＥＳ」である場合も（即ち、ステップ３１０４〜３２０５の処理の結果によるプログラム全体のサイズがステップ３１０２で保存されたサイズよりも小さいならば）、ステップ３１１４へ進む。
【００７４】
ステップ３１１４では、分岐命令と参照ラベルとの距離を計算して、処理を終了する。
以上で、第２実施形態の説明を終了する。
【００７５】
§４．補足
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更等があってもこの発明に含まれる。
たとえば、上述した実施形態においては、分岐命令が変換されるコードの種類が２種類（ショートコードとロングコード）である例を示したが、本発明はこれに限定されず、分岐命令が変換されるコードの種類が３種類以上であっても適用可能である。
【００７６】
【発明の効果】
以上説明したように、この発明によれば、セクションの結合順番を変化させながら最適化を行うので、プログラム全体のサイズを従来よりも更に最適化できる。
【図面の簡単な説明】
【図１】本発明の基本的概念を示す説明図である。
【図２】この発明の第１実施形態による最適化方法の一例を示すフローチャートである。
【図３】この発明の第２実施形態による最適化方法の一例を示すフローチャートである。
【図１】
0003573668.tif 000002
【図２】
0003573668.tif 000003
【図３】
0003573668.tif 000004