(57)【特許請求の範囲】
【請求項１】
高級言語で記述された複数のソースコードからなるプログラムを実行可能コードに変換する装置であって、
前記複数のソースコードを複数のオブジェクトコードに変換する第１の変換手段と、
前記複数のオブジェクトコードを前記実行可能コードに変換する第２の変換手段とを備え、
前記第１の変換手段は、前記複数のソースコードを前記複数のオブジェクトコードに変換する時に、前記複数のオブジェクトコードに含まれる未解決シンボルの出現回数を計測する計測手段を含み、
前記第２の変換手段は、
前記未解決シンボルの出現回数が多い順に前記複数のオブジェクトコードに含まれる前記未解決シンボルに記憶領域を割り当てる記憶領域割り当て手段を備えたことを特徴とするプログラム処理装置。
【請求項２】
前記記憶領域割り当て手段は、プログラム実行中を通して値が保持される変数である前記未解決シンボルの出現回数が多い順に、前記未解決シンボルに記憶領域を割り当てることを特徴とする請求項１に記載のプログラム処理装置。
【請求項３】
前記記憶領域割り当て手段は、副プログラムである前記未解決シンボルの出現回数が多い順に、前記未解決シンボルに記憶領域を割り当てることを特徴とする請求項１に記載のプログラム処理装置。
【請求項４】
前記第１の変換手段は、
前記計測手段が計測した前記未解決シンボルの出現回数を頻度情報ファイルとして出力する頻度情報出力手段を含み、
前記第２の変換手段は、
前記頻度情報出力手段が出力した複数の前記頻度情報ファイルを受け取り、前記未解決シンボル毎に頻度を総計する頻度情報入力手段を含むことを特徴とする請求項１〜３のいずれか１項に記載のプログラム処理装置。
【請求項５】
前記第１の変換手段は、
前記計測手段が計測した前記未解決シンボルの出現回数をオブジェクトコードに付加して出力するオブジェクトコード出力手段を含み、
前記第２の変換手段は、
前記オブジェクトコード出力手段が出力した複数の前記オブジェクトコードを受け取り、前記オブジェクトコードに付加されている前記出現回数を取り出して、前記未解決シンボル毎に頻度を総計する頻度情報入力手段を含むことを特徴とする請求項１〜３のいずれか１項に記載のプログラム処理装置。
【請求項６】
前記指示手段は、
前記記憶領域割り当て手段において前記未解決シンボルに割り当てられた記憶領域を絶対番地形式で操作する命令のコードサイズと前記命令の出現回数の積が、前記未解決シンボルに割り当てられた記憶領域を相対番地形式で操作する命令のコードサイズと前記命令の出現回数の積と前記相対番地をレジスタに設定する命令のコードサイズとの和を上回る場合に、前記未解決シンボルを相対番地アドレス形式で操作する命令を生成するよう、前記第１の変換手段に指示し、
前記第１の変換手段は、
前記指示手段からの指示がある場合に、前記未解決シンボルを相対番地形式で操作する命令を生成することを特徴とする請求項１〜５のいずれか１項に記載のプログラム処理装置。
【請求項７】
高級言語で記述された複数のソースコードからなるプログラムを実行可能コードに変換するプログラムを記録した記録媒体であって、
前記複数のソースコードを複数のオブジェクトコードに変換する時に、前記複数のオブジェクトコードに含まれる未解決シンボルの出現回数を計測する計測ステップを含む第１の変換ステップと、
前記複数のオブジェクトコードを前記実行可能コードに変換し、前記未解決シンボルの出現回数が多い順に前記複数のオブジェクトコードに含まれる前記未解決シンボルに記憶領域を割り当てる記憶領域割り当てステップを含む第２の変換ステップをコンピュータに実行させる為のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高級言語からオブジェクトコードを生成するコンパイラ、複数のオブジェクトコードを連結編集し実行可能コードを生成するリンカ、を含むプログラム処理装置及び記録媒体に関するものであり、特に最終的に生成される実行形式コードのコードサイズを削減するコード最適化技術、及び、変数及びプログラムの記憶領域への配置技術に関する。
【０００２】
【従来の技術】
近年、ますますマイクロコンピュータで処理させるプログラムが複雑・高度化している。これに伴い、プログラムをＣ言語等の高級言語で作成した後、コンパイラおよびリンカによってマイクロコンピュータが実行できる形式に変換する方法が多く用いられるようになってきた。
【０００３】
特に、プログラムが膨大となりつつある昨今では、開発効率の点からプログラムを幾つかのソースコードファイルに分割し、これらを別々にコンパイルした後、リンカにより連結編集し、最終的な機械語コードを生成する分割コンパイルが一般に用いられる。
【０００４】
この分割コンパイルにおける、コンパイラおよびリンカでは、それぞれの連携が重要となる。
【０００５】
以下、従来のコンパイラおよびリンカについて説明する。
特開平９―２１２３６９号公報には、コンパイル時に使用されている変数のサイズを調べ、サイズの小さい順に整列した後で変数をメモリ上に配置する技術が記載されている。これにより基底アドレスからのオフセットの総和が最小に保たれるので記憶領域の削減ができる。また、同公報には、プロファイル情報を使用し、動的なアクセス数の多い順、つまり、実行される回数が多い順に変数を整列した後で、メモリ上に配置する方式も記載されている。これによりアクセス回数の多い変数は小さなオフセットによりアクセスすることができ、アクセス回数の多い変数へのアクセス命令サイズが小さくなり、結果としてコードサイズが削減される。
【０００６】
【発明が解決しようとする課題】
しかしながら、従来の方式では、分割コンパイルされた場合にコードサイズ削減の観点からの最適なメモリ配置を実現することができないという問題点があった。
【０００７】
すなわち、外部変数や静的変数は最終的な機械語コードで１つのみ存在する為、各ファイル内での整列では、最終機械語コードでの最適配置を実現することはできない。
【０００８】
また、プロファイル情報により得られる動的なアクセス数による整列では、一般に、プログラム中のメモリ操作命令の出現数による整列と異なった結果が得られる。コードサイズを削減するためにはプログラムの字面上の命令数が多い、つまり、プログラム中の出現数の多い命令のコードサイズを削減した方が、プログラム全体のコードサイズが小さくなることは明らかであり、コードサイズ改善の余地がある。
【０００９】
更に、プロファイル情報を得るためにはコンパイラはプロファイルを取得する為のコードを生成する必要があり、コンパイル時間、コンパイル時に必要な記憶容量が増大し、また、プロファイルを得る為にプログラムの予備的実行が必要となり、結果、プログラム開発期間の増大を招く。
【００１０】
また、上記方式ではプログラムモジュールの配置については何ら考慮されていない為、副プログラムの呼出命令の最適化は全くなされない。
【００１１】
本発明はかかる問題点に鑑みてなされたものであり、プログラムの予備的実行なしに、分割コンパイルされたプログラムに対しても変数の最適記憶領域配置を実現し、また、プログラムの最適配置を実現することにより、最終コードサイズの削減を果たすプログラム処理装置及び記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
本発明のプログラム処理装置は、
高級言語で記述された複数のソースコードからなるプログラムを実行可能コードに変換する装置であって、
前記複数のソースコードを複数のオブジェクトコードに変換する第１の変換手段と、
前記複数のオブジェクトコードを前記実行可能コードに変換する第２の変換手段とを備え、
前記第１の変換手段は、前記複数のソースコードを前記複数のオブジェクトコードに変換する時に、前記複数のオブジェクトコードに含まれる未解決シンボルの出現回数を計測する計測手段を含み、
前記第２の変換手段は、
前記未解決シンボルの出現回数が多い順に前記複数のオブジェクトコードに含まれる前記未解決シンボルに記憶領域を割り当てる記憶領域割り当て手段を備えたことを特徴とする
【００１５】
また本発明のプログラム処理装置は、前記記憶領域割り当て手段は、プログラム実行中を通して値が保持される変数である前記未解決シンボルの出現回数が多い順に、前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００１８】
また本発明のプログラム処理装置は、前記記憶領域割り当て手段は、実体が副プログラムである前記未解決シンボルの出現回数が多い順に、前記未解決シンボルに記憶領域を割り当てることを特徴とすることができる。
【００１９】
本発明のプログラム処理装置は、第１の変換手段は、前記計測手段が計測した前記未解決シンボルの出現回数を頻度情報ファイルとして出力する頻度情報出力手段を含み、前記第２の変換手段は、前記頻度情報出力手段が出力した複数の前記頻度情報ファイルを受け取り、前記未解決シンボル毎に頻度を総計する頻度情報入力手段を含むとすることができる。
【００２０】
また本発明のプログラム処理装置は、前記第１の変換手段は、前記計測手段が計測した前記未解決シンボルの出現回数をオブジェクトコードに付加して出力するオブジェクトコード出力手段を含み、前記第２の変換手段は、前記オブジェクトコード出力手段が出力した複数の前記オブジェクトコードを受け取り、前記オブジェクトコードに付加されている前記出現回数を取り出して、前記未解決シンボル毎に頻度を総計する頻度情報入力手段を含むとすることができる。
【００２２】
また本発明のプログラム処理装置は、前記指示手段は、前記記憶領域割り当て手段において前記未解決シンボルに割り当てられた記憶領域を絶対番地形式で操作する命令のコードサイズと前記命令の出現回数の積が、前記未解決シンボルに割り当てられた記憶領域を相対番地形式で操作する命令のコードサイズと前記命令の出現回数の積と前記相対番地をレジスタに設定する命令のコードサイズとの和を上回る場合に、前記未解決シンボルを相対番地アドレス形式で操作する命令を生成するよう、前記第１の変換手段に指示し、前記第１の変換手段は、前記指示手段からの指示がある場合に、前記未解決シンボルを相対番地形式で操作する命令を生成するとすることができる。
【００２３】
また本発明の記録媒体は、高級言語で記述された複数のソースコードからなるプログラムを実行可能コードに変換するプログラムを記録した記録媒体であって、前記複数のソースコードを複数のオブジェクトコードに変換する時に、前記複数のオブジェクトコードに含まれる未解決シンボルの出現回数を計測する計測ステップを含む第１の変換ステップと、前記複数のオブジェクトコードを前記実行可能コードに変換し、前記未解決シンボルの出現回数が多い順に前記複数のオブジェクトコードに含まれる前記未解決シンボルに記憶領域を割り当てる記憶領域割り当てステップを含む第２の変換ステップをコンピュータに実行させる為のプログラムを記録するとすることができる。
【００２４】
【発明の実施の形態】
以下、本発明に係るプログラム処理装置及び記録媒体について図面を参照しながら説明する。
［用語の説明］
まず初めに本説明で用いる用語の説明を行なう。
・副プログラム
メインルーチンから呼び出されるプログラム。具体的には、関数やサブルーチンを指す。
・未解決シンボル
オブジェクトコードが連結編集されるまで確定しないシンボル。外部変数や外部ラベル（副プログラムの開始アドレス）などがある。
・オブジェクト
シンボルが表す実体。例えば、高級言語としてＣ言語を用いた場合、ＡがＬＯＮＧ型の外部変数である場合、実体は８バイトのメモリとなる。
・セクション
連結編集の際に、オブジェクトを配置する時の区別。同じセクションのオブジェクトは一まとめにされて配置される。一般にプログラムはコードセクションとして、変数はデータセクションとしてまとめて配置される。
［１．実施の形態１］
［プログラム処理装置の構成］
図１は、本プログラム処理装置の構成及び関連するデータを示すブロック図である。
【００２５】
本プログラム処理装置は、大きく２つのグループ、即ち、（１）高級言語で書かれたソースコード５０からオブジェクトコード６０を生成するグループ（コンパイラ上流部１０、コード生成部１１、頻度情報出力部１２、頻度測定部１３からなる変換手段１、以下コンパイラと呼ぶ）と、（２）複数のオブジェクトコード６０〜６１を連結編集し最終の実行可能コード７０を生成するグループ（シンボル情報収集部２０、頻度情報入力部２１、配置最適化部２２、記憶領域割り付け部２３からなる変換手段２、以下リンカと呼ぶ）から構成される。
（コンパイラ上流部１０）
コンパイラ上流部１０は、ファイル形式で保存されている高級言語ソースコード５０を読み込み、構文解析及び意味解析を行なった後に内部形式コードを生成する。更に、必要に応じて、最終的に生成される実行可能コードのサイズやその実行時間が短くなるようにその内部形式コードを最適化する。ここでの処理は、従来のコンパイラが有するコンパイラ上流部による処理と同一である。
（コード生成部１１）
コード生成部１１は、コンパイラ上流部１０により生成され最適化された内部形式コードからオブジェクトコード６０を生成する。ここで、「オブジェクトコード」とは、再配置可能情報を含んだ目的機械向け機械語プログラムである。コード生成部１１は頻度測定部１３を含む。頻度測定部１３はコード生成部で生成されたコードに未解決シンボルが含まれていた場合にシンボル頻度情報テーブル１４にアクセスしてシンボルの出現頻度を更新する。
【００２６】
コード生成部１１の処理の詳細は以下の通りである。
図２は、コード生成部１１での処理手順を示すフローチャートである。
【００２７】
コード生成部１１は、コンパイラ上流部１０が生成した内部形式コードの全ての命令について、以下の処理（ステップＳ２〜Ｓ６）を繰り返す（ステップＳ１、Ｓ７）。
【００２８】
まず、コード生成部１１は、着目する内部形式コード命令に対応する機械語コード命令（以下、単に「着目命令」と呼ぶ。）を生成する（ステップＳ２）。
【００２９】
次に、着目命令が未解決シンボルを含むか否かを判断する（ステップＳ３）。未解決シンボルを含む場合には、更にその未解決シンボルが既にシンボル頻度情報テーブルに登録済みか否かを判断する（ステップＳ４）。
【００３０】
未解決シンボルがシンボル頻度情報テーブルに登録されていない場合には、当該未解決シンボルに対応するエントリを、シンボル頻度情報テーブルに作る（ステップＳ５）。その際、当該シンボルの使用頻度を０に初期化する。
【００３１】
次に当該シンボルの使用頻度に１を加え、シンボル頻度情報テーブルを更新する（ステップＳ６）。
【００３２】
なお、図２中、点線で囲まれる部分がコード生成部１１に含まれる頻度測定部１３の処理に相当する。
（頻度情報出力部１２）
図１に戻って、頻度情報出力部１２は、シンボル頻度情報テーブル１４を読み出し、シンボル頻度情報ファイル８０として出力する。
【００３３】
以上コンパイラ１の処理によりソースコード５０からこれに対応したオブジェクトコード６０とシンボル頻度情報ファイル８０が生成される。ソースコードが複数ある場合には、コンパイラ１の処理をそれぞれのソースコード５０、５１に対して行なうことにより、それぞれに対応したオブジェクトコード６０、６１とシンボル頻度情報ファイル８０、８１が生成される。
（シンボル情報収集部２０）
シンボル情報収集部２０は、複数のオブジェクトコード６０〜６１を読み込みシンボル情報を収集する。更に、収集されたシンボル情報に基づき、シンボル情報テーブル２４を生成する。ここでの処理は、従来のリンカが有するシンボル情報収集部による処理と同一である。また、生成されるシンボル情報テーブル２４も、この段階では、従来のリンカが生成するシンボル情報テーブル２４と違いはない。
（頻度情報入力部２１）
頻度情報入力部２１は、コンパイラ１の頻度情報出力部１２が出力したシンボル頻度情報ファイル８０〜８１を読み込み。シンボル情報収集部２０が生成したシンボル情報テーブル２４の対応するエントリに、シンボル頻度情報を追加する。
（配置最適化部２２）
配置最適化部２２は、シンボル情報テーブル２４を参照し変数のメモリ配置を最適化する。具体的にはシンボルの使用頻度に着目し、使用頻度の多い変数を記憶領域の基底アドレスに近い位置に配置する。これにより頻繁にアクセスされるメモリに対するコードが小さくなることが期待されるので全体としてコードサイズを小さくすることが可能となる。
【００３４】
配置最適化部２２の処理の詳細は以下の通りである。
図３は、配置最適化部２２での処理手順を示すフローチャートである。
【００３５】
まず配置最適化部２２は、シンボル情報テーブルを頻度数の多い順に整列する（ステップＴ１）。整列はセクション毎に行なう。
【００３６】
次に、以下の処理で用いる割り付け可能メモリ位置を、割り付け可能なメモリの先頭に初期化する（ステップＴ２）。この割り付け可能メモリ位置はセクション数により複数個用意される。当実施の形態では外部及び静的変数用割り付け可能メモリ位置（以下、変数用割り付け可能メモリ位置と呼ぶ）とプログラム用割り付け可能メモリ位置の２つを使用するものとする。
【００３７】
次に配置最適化部２２は、シンボル情報テーブルに従い割り付け対象がある間、ステップＴ１で整列された順に従って以下の処理（ステップＴ４〜Ｔ５）を繰り返す（ステップＴ３、Ｔ６）。
【００３８】
未解決シンボルを割り付け可能メモリ位置に割り付け、割り付けたメモリ位置をシンボル情報テーブル２４に登録する（ステップＴ４）。この際、割り付け対象の未解決シンボルが変数である場合には変数用割り付け可能メモリ位置を、プログラムである場合にはプログラム用割り付け可能メモリ位置を使用する。
【００３９】
次に、割り付け可能メモリ位置を、ステップＴ４で割り付けたオブジェクトのサイズに従って更新する（ステップＴ５）。具体的には現在の割り付け可能メモリ位置にステップＴ４で割り付けたオブジェクトのサイズを加えて、新たな割り付け可能メモリ位置とする。目的機械の制限によりメモリアライメントに制約のある場合には、これを考慮して新たな割り付け可能メモリ位置を調整する。この際、ステップＴ４で割り付けた未解決シンボルが変数である場合には変数用割り付け可能メモリ位置を、プログラムである場合にはプログラム用割り付け可能メモリ位置を更新する。
（記憶領域割り付け部２３）
図１に戻って、記憶領域割り付け部２３は、配置最適化部２２で決定された内容に従って、実際にメモリを割り付け、最終実行可能コード７０を生成する。生成された実行可能コード７０はファイルとして書き出される。
［プログラム処理装置の具体的な動作］
次に、本プログラム処理装置の特徴的な構成要素の動作について、具体的な命令を用いて説明する。
【００４０】
まず、本プログラム処理装置が対象とする目的機械について説明する。一般に固定長命令アーキテクチャにおいては１つの命令でアクセスできるメモリ範囲は限られている。図４（ａ）に示すのは固定長命令アーキテクチャにおけるメモリアクセス命令の一例である。このようなメモリアクセス命令を持つ目的機械においてはメモリを指定するアドレスを表現する幅が１６ビットしかないため、０番地から６５５３５番地までの６５５３６バイトの領域までしか１つの命令で表すことはできない（矢符ａ１）。この範囲を越えるメモリには２つ以上の命令で表現する必要がある（矢符ａ２）。副プログラム呼出命令についてはある範囲までの領域しか直接呼び出すことはできない（矢符ａ３）。また一方、可変長命令アーキテクチャにおいても同様の制限が存在する。図４（ｂ）に示すのは可変長命令アーキテクチャにおける命令の一例である。この例では２バイト命令ではアドレス幅８ビット、すなわち、０番地から２５５番地までの２５６バイトの領域にアクセスすることができる（矢符ａ４）。同様に３バイト命令では６５５３５番地（矢符ａ５）、４バイト命令では４２９４９６７２９５番地までの領域にアクセスすることができる（矢符ａ６）。つまり、可変長アーキテクチャでは１つの命令で全てのメモリ領域にアクセスすることができるが、アクセスする領域が０番地から離れるに従いコードサイズが増大することになる。副プログラムに対する呼出命令でも同様により広いメモリ領域に対する呼出命令は、命令サイズより大きくなる（矢符ａ７、ａ８）。なお、ここでは絶対番地形式のメモリアクセス命令を例としてあげているが、これが相対番地形式であっても同じことがいえる。相対番地形式の場合には基準が０番地ではなく基底レジスタの値であるという違いがあるだけで、基底レジスタから離れるに従い、必要なコードサイズは増大する。
［例］
プログラムが３つに分割コンパイルされる場合について例を用いて説明する。この場合、ソースコードは３つ存在することになる。
【００４１】
まず、第１のソースコードがコンパイルされる。コンパイラに入力されたソースコードは、コンパイラ上流部１０で処理され内部形式コードに変換される。ここでは図５（ａ）の内部形式コードが得られたとする。内部形式コードは次にコード生成部１１に入力される。コード生成部１１の動作について、図２に示されたフローチャートに沿って説明する。
【００４２】
コード生成部１１は内部形式コードがある間、ステップＳ１〜Ｓ７を繰り返す。
【００４３】
まず命令ｃ１が図５（ｂ）の機械語コードｍ１に変換される（ステップＳ２）。
【００４４】
続いてこの命令が未解決シンボルを含むか否かが判断される（ステップＳ３）。機械語コードｍ１に含まれるシンボルｍｅｍｏｒｙ１は未解決シンボルであるのでＹｅｓと判断される。
【００４５】
次にこのシンボルが既にシンボル頻度情報テーブル１４に登録されているかが判断される（ステップＳ４）。この機械語コードｍ１はこのソースコードを処理した最初の命令であるのでシンボル頻度情報には何も登録されていない。このためこの分岐はＮｏと判断される。
【００４６】
次に未解決なシンボルｍｅｍｏｒｙ１をシンボル頻度情報テーブルに登録する（ステップＳ５）。具体的には、シンボル頻度情報テーブル１４にシンボルｍｅｍｏｒｙ１の欄を作り、頻度を０に初期化する（図６（ａ））。
【００４７】
最後に現在取り扱っているシンボルｍｅｍｏｒｙ１の使用頻度に１を加え、シンボル頻度情報テーブルを更新する（ステップＳ６）。シンボル頻度情報テーブル１４は図６（ｂ）になる。
【００４８】
以上のステップを内部形式コードがある間繰り返す（ステップＳ７）。
内部形式コードｃ２、ｃ３が処理された直後のシンボル頻度情報テーブルの内容を図６（ｃ）、（ｄ）に示す。内部形式コードｃ２、ｃ３はそれぞれ機械語コードｍ２、ｍ３に変換される。また、第１のソースコードの処理が終った後での、シンボル頻度情報テーブルの内容を図６（ｅ）に示す。ここで図６（ｄ）、（ｅ）でのｆｕｎｃｔｉｏｎ１の上の切れ目はこれより上が変数に対するシンボル頻度情報を、これより下が副プログラムに対するシンボル頻度情報を表していることを示している。これらはそれぞれ変数用とプログラム用のセクションを形成する。
【００４９】
コード生成部１１の処理が終ると、制御は頻度情報出力部１２に移る。頻度情報出力部１２はシンボル頻度情報テーブルを参照して、その内容をシンボル頻度情報ファイル８０として出力する。第１のソースコードに対応するシンボル情報ファイル８０の内容を図７（ａ）に示す。
【００５０】
第２、第３のソースコードについても同様の処理が行なわれる。第２、第３のソースコードに対応するシンボル頻度情報ファイルの内容は図７（ｂ）、（ｃ）の通りであるとする。ここで図７（ａ）〜（ｃ）でのｆｕｎｃｔｉｏｎ１の上の切れ目はこれより上が変数に対するシンボル頻度情報を、これより下が副プログラムに対するシンボル頻度情報を表していることを示している。
【００５１】
次にリンカの処理内容について説明する。まず、シンボル情報収集部２０がコンパイラより出力された複数のオブジェクトファイル６０〜６１を読み込む。この際、シンボルが出現した順にシンボル情報テーブル２４にエントリを生成し、リンク処理に必要な情報（オブジェクトサイズ、アライメント情報）を取り込む。これらの情報は一般にオブジェクトファイルに含まれる。この処理は従来のリンカでの処理と違いはないので詳細は省略する。この例では３つのソースコードに対応する３つのオブジェクトコードが読み込まれ、図８（ａ）に示すシンボル情報テーブルに形成される。
【００５２】
次に頻度情報入力部２１が起動される。頻度情報入力部２１は、シンボル情報収集部２０が読み込んだオブジェクトファイルに対応する複数のシンボル頻度情報ファイル８０〜８１を読み込み、シンボル情報テーブル２４内各シンボルのエントリの頻度欄に、読み込んだ頻度情報ファイルに記述されている値を加算する。この例では図７（ａ）、（ｂ）、（ｃ）に示す３つのシンボル頻度情報ファイルを読み込み、結果、シンボル情報テーブルは図８（ｂ）の様になる。
【００５３】
頻度情報入力部２１の処理が終ると、配置最適化部２２が起動される。配置最適化部２２の動作について、図３に示されたフローチャートに沿って説明する。
【００５４】
まず、シンボル情報テーブルをセクション毎に頻度数の多い順に整列（ソート）する（ステップＴ１）。セクションは図８（ａ）、（ｂ）、（ｃ）中のｆｕｎｃｔｉｏｎ１欄の上の切れ目で分かれ、計２セクション存在する。この結果、シンボル情報テーブル２４は図８（ｃ）の様になる。
【００５５】
次に割り付け可能メモリ位置を初期化する（ステップＴ２）。ここではプログラム用割り付け可能メモリ位置を０ｘＦ０００番地に、変数用割り付け可能メモリ位置を０ｘ００Ｆ０に初期化したとする。０ｘは後ろの数値が１６進数表記であることを示す。これは以下でも同様である。
【００５６】
割り付け対象がある間、ステップＴ４〜Ｔ５を繰り返す（ステップＴ３、Ｔ６）。
【００５７】
次に、未解決シンボルをメモリに割り付ける（ステップＴ４）。シンボル情報テーブルの先頭の未解決シンボルはｍｅｍｏｒｙ３であるのでこれを０ｘ００Ｆ０番地に割り付ける。
【００５８】
最後に、割り付けたオブジェクトのサイズに従って割り付け可能メモリ位置を更新する（ステップＴ５）。ここでｍｅｍｏｒｙ１のサイズは０ｘ０００８であるので割り付け可能メモリ位置は０ｘ００Ｆ８となる。
【００５９】
割り付け対象が残っている間、上記ステップＴ３〜Ｔ６が繰り返し実行される。残りのオブジェクトに対する割り付け動作について簡単に示す。
【００６０】
２番目の未解決シンボルはｍｅｍｏｒｙ２である。これは０ｘ００Ｆ８番地に割り付けられ（ステップＴ４）、割り付け可能メモリ位置はｍｅｍｏｒｙ２のオブジェクトサイズ０ｘ０００８を加えて０ｘ０１００に更新される（ステップＴ５）。
【００６１】
３番目の未解決シンボルはｍｅｍｏｒｙ１である。これは０ｘ０１００番地に割り付けられ（ステップＴ４）、割り付け可能メモリ位置はｍｅｍｏｒｙ１のオブジェクトサイズ０ｘ０００８を加えて０ｘ０１０８に更新される（ステップＴ５）。
【００６２】
４番目の未解決シンボルはｆｕｎｃｔｉｏｎ２である。これはプログラムであるので、プログラム用割り付け可能メモリ位置を参照して、０ｘＦ０００番地に割り付けられる（ステップＴ４）。割り付け可能メモリ位置はｆｕｎｃｔｉｏｎ２のオブジェクトサイズ０ｘ０１２０を加えて０ｘＦ１２０に更新される（ステップＴ５）。
【００６３】
５番目の未解決シンボルはｆｕｎｃｔｉｏｎ１である。これもプログラムであるので、０ｘＦ１２０番地に割り付けられ（ステップＴ４）、割り付け可能メモリ位置はｆｕｎｃｔｉｏｎ１のオブジェクトサイズ０ｘ２１３４を加えて０ｘ１１２５４に更新される（ステップＴ５）。
【００６４】
配置最適化部２２終了段階でのシンボル情報テーブルは図９の様になる。
最後に、記憶領域割り付け部２３がシンボル情報テーブル２４の内容に従い、入力されたオブジェクトコード中の未解決シンボルを配置先アドレスで書き換える。この処理は従来のリンカの処理と同じである。
【００６５】
以上の処理により最終的な実行可能コードが得られる。この例では３つのソースコードから生成された３つのオブジェクトコードを連結編集して実行可能コードが生成される。生成された実行可能コードの一部を図５（ｃ）に示す。図５（ｃ）に示すのは実行可能コードの内、図５（ａ）、（ｂ）に示した第１のソースコードに対応する部分をニーモニックで表記したものである。実際の実行可能コードにはこれ以外に第２、第３のソースコードに相当する部分が含まれる。図５（ｂ）と比較して分かるように図５（ｂ）での未解決シンボルが、シンボル情報テーブル（図９）で確定した実際のメモリアドレスで置き換えられていることが分かる。
【００６６】
次に本実施の形態１に基づき生成された実行可能コードのコードサイズを示す。目的機械にアーキテクチャとして図４（ｂ）の可変長命令アーキテクチャを想定すると、第１、第２、第３のソースコード全てを含めたプログラム全体で最も頻繁にアクセスされるメモリｍｅｍｏｒｙ３へのアクセス命令は、メモリｍｅｍｏｒｙ３が０ｘ００Ｆ０番地に配置されるので２バイト命令となり、メモリアクセス命令のコード総計は２０バイトとなる。全てのメモリアクセス命令について考慮すると、本実施の形態１では２×１０＋２×６＋４×５＝５２バイトとなる。
【００６７】
また副プログラムの配置においては、ｆｕｎｃｔｉｏｎ１の呼出はｆｕｎｃｔｉｏｎ１が０ｘＦ１２０番地から配置されるので４バイト命令、ｆｕｎｃｔｉｏｎ２の呼出もｆｕｎｃｔｉｏｎ２が０ｘＦ０００番地から配置されるので４バイト命令となり、呼出命令全体では４×５＋４×７＝４８バイトとなる。
【００６８】
各命令のサイズを示す為に、図５（ｃ）には第１のソースコード相当部分のコードサイズを各命令ニーモニックの右横に示した。第１のソースコード相当部分のコードサイズは３０バイトとなる。
【００６９】
なお、この実施の形態ではシンボル頻度情報テーブル１４の内容を頻度情報ファイル８０として出力してリンカに渡したが、コード生成部１１が生成するオブジェクトコード６０にシンボル頻度情報テーブル１４の内容を付加してリンカに受け渡しても良い。
【００７０】
また、ｍｅｍｏｒｙ１へのアクセス命令のように命令コードサイズ（４バイト）と出現頻度（５回）の積（２０バイト）がｍｅｍｏｒｙ１への相対番地アドレス形式メモリアクセス命令のコードサイズ（２バイト、図４（ｂ）矢符ａ９）と出現頻度（５回）の積（１０バイト）と相対番地アドレス基底レジスタへの設定命令（６バイト、図４（ｂ）矢符ａ１０）との和（１６バイト）を上回る場合には、対応する未解決シンボル（この場合ｍｅｍｏｒｙ１）を相対番地形式で出力するようにコード生成部１１へ指示し、コード生成から再度繰り返すようにしても良い。これにより更にコードサイズが削減できる。
［従来のプログラム処理装置との比較］
以上の処理により、最終的な実行可能コードが得られる。本発明の特徴を明確に示す為に、従来のプログラム処理装置（コンパイラ及びリンカ）での場合と比較する。
【００７１】
図１３は従来のプログラム処理装置の構成を本発明の実施の形態と対比して示すブロック図である。
【００７２】
このプログラム処理装置では、本実施の形態の頻度測定部１３、頻度情報出力部１２、頻度情報入力部２１、配置最適化部２２を備えていない。従って複数のオブジェクトファイルに表れる未解決シンボルの出現頻度を得る手段がなく、リンカが処理する場合、未解決シンボルの出現順にメモリを割り当てることになる。このため、第１〜第３のソースコードを処理した場合の各シンボルに割り当てられるメモリは図１４の様になる。なお、図１４では以下での比較の為に出現頻度を付記しているが従来の構成では出現頻度欄は存在しない。
【００７３】
次に、従来のプログラム処理装置に基づき生成された実行可能コードのコードサイズを示す。本実施の形態１と同じく、目的機械にアーキテクチャとして図４（ｂ）の可変長命令アーキテクチャを想定すると、最も頻繁にアクセスされるメモリｍｅｍｏｒｙ３へのアクセス命令は、ｍｅｍｏｒｙ３が０ｘ０１００番地に配置されるので４バイト命令となり、この命令が１０回出現することから、このメモリへのアクセス命令のコード総計は４０バイトとなる。これは本実施の形態１のプログラム処理装置での結果より、２０バイト増加している。全てのメモリアクセス命令について考慮すると、従来例では２×５＋２×６＋４×１０＝６２バイトとなり、本実施の形態１での結果である５２バイトに比べ１０バイトの増加となる。
【００７４】
また、副プログラムの配置においても同様の効果が表れる。従来例ではｆｕｎｃｔｉｏｎ１の呼出はｆｕｎｃｔｉｏｎ１が０ｘＦ０００番地から配置されるので２バイト命令、ｆｕｎｃｔｉｏｎ２の呼出はｆｕｎｃｔｉｏｎ２が０ｘ１１１３４番地から配置されるので４バイト命令となり、呼出命令全体では４×５＋６×７＝６２バイトとなる。これに対し本実施の形態１では、呼出命令全体でのコードサイズは４８バイトであったので、従来例では本実施の形態１に比べコードサイズが１４バイト増加することになる。
【００７５】
なお、従来のプログラム処理装置に変数のサイズもしくは動的使用頻度に基づく自動変数の記憶領域割り付けを行なう手段が備わっている場合でも、この例で示すような複数ファイルに分割されたプログラムの外部変数に対しては、記憶領域割り付けの最適化ができないことはいうまでもない。
［２．実施の形態２］
［プログラム処理装置の構成］
図１０は、本プログラム処理装置の実施の形態２における構成及び関連するデータを示すブロック図である。
【００７６】
本プログラム処理装置は、大きく２つのグループ、即ち、（１）高級言語で書かれたソースコード１５０からオブジェクトコード１６０を生成するグループ（コンパイラ上流部１１０、コード生成部１１１からなるコンパイラ１０１）と、（２）複数のオブジェクトコード１６０〜１６１を連結編集し最終の実行可能コード１７０を生成するグループ（シンボル情報収集部１２０、頻度測定部１２１、配置最適化部１２２、記憶領域割り付け部１２３からなるリンカ１０２）から構成される。
（コンパイラ上流部１１０）
これは実施の形態１におけるコンパイラ上流部１０と同一である。
（コード生成部１１１）
コード生成部１１１は、コンパイラ上流部１１０により生成され最適化された内部形式コードからオブジェクトコード１６０を生成する。ここで、「オブジェクトコード」とは、再配置可能情報を含んだ目的機械向け機械語プログラムである。
（シンボル情報収集部１２０）
これは実施の形態１におけるシンボル情報収集部２０と同一である。
（頻度測定部１２１）
頻度測定部１２１は、シンボル情報収集部１２０が読み込んだ複数のオブジェクトコード１６０〜１６１をサーチし、シンボル情報収集部１２０が生成したシンボル情報テーブル１２４の各シンボルについて、シンボルの出現頻度を測定する。
【００７７】
頻度測定部１２１の処理の詳細は以下の通りである。
図１１は、頻度測定部１２１での処理手順を示すフローチャートである。
【００７８】
まず、頻度測定部１２１は、シンボル情報テーブル１２４の頻度欄を全て０で初期化する（ステップＵ１）。
【００７９】
次に、オブジェクトコード中のプログラムに相当する部分がある間以下の処理（ステップＵ３〜Ｕ４）を繰り返す（ステップＵ２、Ｕ５）。
【００８０】
まず、現在処理している命令が未解決シンボルを含むか否かを判定する（ステップＵ３）。含まない場合はステップＵ５へ移行し、次の命令の処理に移る。
【００８１】
未解決シンボルを含む場合には、シンボル情報テーブルの当該シンボル行の頻度欄に１を加える（ステップＵ４）。
【００８２】
以上の処理を繰り返し、リンカに入力された全てのオブジェクトコードに対する各シンボルの頻度情報が得られる。
（配置最適化部１２２）
これは実施の形態１における配置最適化部２２と同一である。
（記憶領域割り付け部１２３）
これは実施の形態１における記憶領域割り付け部２３と同一である。
［プログラム処理装置の具体的な動作］
次に、実施の形態２における本プログラム処理装置の特徴的な構成要素の動作について、具体的な命令を用いて説明する。プログラムが３つに分割コンパイルされる場合について例を用いて説明する。この場合、ソースコードは３つ存在することになる。
【００８３】
変換手段１については、従来のコンパイラと同等であるので動作については省略し、実施の形態１と同じ第１〜第３のソースコードを処理し、３つのオブジェクトコードが得られたとする。
【００８４】
リンカの処理内容について説明する。まず、シンボル情報収集部１２０がコンパイラより出力された複数のオブジェクトファイル１６０〜１６１を読み込む。この際、シンボルが出現した順にシンボル情報テーブル１２４にエントリを生成し、リンク処理に必要な情報（オブジェクトサイズ、アライメント情報）を取り込む。これらの情報は一般にオブジェクトファイルに含まれる。この処理は従来のリンカでの処理と違いはないので詳細は省略する。この例では３つのオブジェクトコードが読み込まれ、図１２（ａ）に示すシンボル情報テーブルに形成される。
【００８５】
次に頻度測定部１２１が起動される。頻度測定部１２１は、シンボル情報収集部１２０が読み込んだ複数オブジェクトファイルのプログラム部分を調べ、各未解決シンボルの静的出現頻度を測定する。まず、シンボル情報テーブル１２４の頻度欄を０に初期化する（ステップＵ１、図１２（ｂ））。次にプログラム部分がある間未解決シンボルをサーチし、未解決シンボルが出現する度に対応する頻度欄に１を加える（ステップＵ２〜Ｕ５）。３つのオブジェクトコードに含まれるプログラム部分全ての処理が終った後のシンボル情報テーブル１２４は図１２（ｃ）の様になる。
【００８６】
次に配置最適化部１２２、記憶領域割り付け部１２３が順に起動される。図１２（ｃ）は実施の形態１の図８（ｂ）と全く同一なので、配置最適化部１２２、記憶領域割り付け部１２３での処理も実施の形態１での配置最適化部２２、記憶領域割り付け部２３での処理と同じ結果となり、最終的に、実施の形態１と同じ記憶領域割り付けが実現する。
［３．実施の形態３］
実施の形態１、２で示されるプログラム処理装置をフロッピーディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯなどの記録媒体に入れることにより実施の形態１、２で示されるプログラム処理装置を、コンピューターで実現できる。
【００８７】
【発明の効果】
以上の説明から明らかなように、本発明に係るプログラム処理装置は、高級言語で記述された複数のソースコードからなるプログラムを実行可能コードに変換する装置であって、ソースコードを目的コードに変換する変換手段１と、オブジェクトコードを実行可能コードに変換する変換手段２とを備え、変換手段２は前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てる記憶領域割り当て手段を備えることを特徴とする。
【００８８】
これにより、ソースプログラム中の変数や副プログラムのうち頻繁に操作されるものが、基底アドレスに近い領域に配置されるので、これらを操作する命令のサイズが短縮され、結果、プログラム全体のコードサイズを圧縮することができる。
【００８９】
ここで、前記変換手段１は未解決シンボルの出現手段を計測する計測手段１を含み、前記記憶領域割り当て手段は、前記計測手段１が計測した前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００９０】
これによって、各ソースプログラム中の未解決シンボルの出現頻度がコンパイル時にコード生成と同時に計測されるので、記憶領域最適化機能を実現したリンク処理を、大きな付加時間なしに完了することができる。
【００９１】
また、前記変換手段２が未解決シンボルの出現手段を計測する計測手段２を含み、前記記憶領域割り当て手段は、前記計測手段２が計測した前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００９２】
これによって、プログラム中の未解決シンボルの出現頻度が既存のコンパイラの出力するオブジェクトコードから計測することができるようになるので、既存のコンパイラ及び既存のコンパイラが出力したオブジェクトコードを活用しつつ記憶領域配置の最適化を行ない、コードサイズの削減をすることが可能となる。
【００９３】
また、前記記憶領域割り当て手段は、プログラムを構成する複数のソースコード全体に渡って有効な変数である前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００９４】
これによって、頻繁に操作される外部変数に対する操作命令の命令サイズが短縮されるので、プログラム全体のコードサイズを削減することができる。
【００９５】
また、前記記憶領域割り当て手段は、プログラムを構成する複数のソースコードのうち、いずれか１つのソースコードファイル全体に渡って有効な変数である前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００９６】
これによって、頻繁に操作されるファイル内静的変数に対する操作命令の命令サイズが短縮されるので、プログラム全体のコードサイズを削減することができる。
【００９７】
また、前記記憶領域割り当て手段は、プログラムを構成する複数のソースコードのうち、いずれか１つのソースコードのある一部で有効であり、且つ、プログラム実行中を通して値が保持される変数である前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【００９８】
これによって、頻繁に操作される静的変数に対する操作命令の命令サイズが短縮されるので、プログラム全体のコードサイズを削減することができる。
【００９９】
また、前記記憶領域割り当て手段は、副プログラムである前記未解決シンボルの出現回数が多い順に前記未解決シンボルに記憶領域を割り当てるとすることができる。
【０１００】
これによって、頻繁に呼び出される副プログラムに対する呼出命令の命令サイズが短縮されるので、プログラム全体のコードサイズを削減することができる。
【０１０１】
また本発明のプログラム処理装置は、前記指示手段は、前記記憶領域割り当て手段において前記未解決シンボルに割り当てられた記憶領域を絶対番地形式で操作する命令のコードサイズと前記命令の出現回数の積が、前記未解決シンボルに割り当てられた記憶領域を相対番地形式で操作する命令のコード回数と前記命令の出現回数の積と前記相対番地アドレスをレジスタに設定する命令のコードサイズとの和を上回る場合に、前記未解決シンボルを相対番地アドレス形式で操作する命令を生成するよう、前記変換手段１に指示し、前記変換手段１は、前記指示手段からの指示がある場合に、前記未解決シンボルを相対番地形アドレス式で操作する命令を生成するとすることができる。
【０１０２】
これによってアドレスを絶対番地形式より相対番地形式で表した方がコードサイズが小さくなる場合を的確に判断して、更にコードサイズを削減することができる。
【図面の簡単な説明】
【図１】本発明の第一の実施の形態を示すコンパイラ、リンカの構成及び関連するデータを示すブロック図
【図２】本プログラム処理装置のコード生成部１１での処理手順を示すフローチャート
【図３】本プログラム処理装置の配置最適化部２２での処理手順を示すフローチャート
【図４】本発明に係るプログラム処理装置が対象とする固定長命令セットの一例を示す図
【図５】本プログラム処理装置のコンパイラ上流部１０が生成した内部形式コードの一例を示す図
【図６】生成途中のシンボル頻度情報テーブル１４の一例を示す図
【図７】第１〜３のソースコードに対応するシンボル頻度情報ファイルの一例を示す図
【図８】処理途中のシンボル情報テーブル２４の一例を示す図
【図９】配置最適化部２２での処理が完了したシンボル情報テーブル２４の一例を示す図
【図１０】本発明の第二の実施の形態を示すコンパイラ、リンカの構成及び関連するデータを示すブロック図
【図１１】本発明の第二の実施の形態におけるプログラム処理装置の頻度測定部１２１での処理手順を示すフローチャート
【図１２】シンボル情報収集部１２０で生成されたシンボル情報テーブル１２４の一例を示す図
【図１３】従来のプログラム処理装置の構成及び関連データを示すブロック図
【図１４】従来のプログラム処理装置におけるシンボル情報収集部９０２処理完了後のシンボル情報テーブル９８０の一例を示す図
【符号の説明】
１  コンパイラ
２  リンカ
１０  コンパイラ上流部
１１  コード生成部
１２  頻度情報出力部
１３  頻度測定部
１４  シンボル頻度情報テーブル
２０  シンボル情報収集部
２１  頻度情報入力部
２２  配置最適化部
２３  記憶領域割り付け部
２４  シンボル情報テーブル
５０、５１  ソースコード
６０、６１  オブジェクトコード
７０  実行可能コード
８０、８１  シンボル頻度情報
１０１  コンパイラ
１０２  リンカ
１１０  コンパイラ上流部
１１１  コード生成部
１２０  シンボル情報収集部
１２１  頻度測定部
１２２  配置最適化部
１２３  記憶領域割り付け部
１２４  シンボル情報テーブル
１５０  ソースコード
１６０、１６１  オブジェクトコード
１７０  実行可能コード
９００  コンパイラ上流部
９０１  コード生成部
９０２  シンボル情報収集部
９０３  記憶領域割り付け部
９５０  ソースコード
９６０、９６１  オブジェクトコード
９７０  実行可能コード
９８０  シンボル情報テーブル
【図１】
0003675166.tif 000002
【図２】
0003675166.tif 000003
【図３】
0003675166.tif 000004
【図４】
0003675166.tif 000005
【図５】
0003675166.tif 000006
【図６】
0003675166.tif 000007
【図７】
0003675166.tif 000008
【図８】
0003675166.tif 000009
【図９】
0003675166.tif 000010
【図１０】
0003675166.tif 000011
【図１１】
0003675166.tif 000012
【図１２】
0003675166.tif 000013
【図１３】
0003675166.tif 000014
【図１４】
0003675166.tif 000015