(57)【要約】【課題】  動的データ領域を使用効率良く管理する記憶域管理装置および記憶域管理方法を提供する。【解決手段】  動的データ領域管理システム１は、中間プログラム２に含まれる関数呼び出し命令を関数呼び出し命令検索手段１１により検索する。関数呼び出し命令が検出されると、その関数に対して、局所変数検索手段１２による局所変数の検索、ヒープ領域確保命令検索手段１３によるヒープ領域確保命令の検索、ヒープ領域解放命令検索手段１４によるヒープ領域解放命令の検索を行い、それぞれの検索結果に基づいて、動的データ領域管理情報生成手段１５が動的データ領域管理情報３を生成する。この動的データ領域管理情報３をスタック領域に格納することにより、スタック領域の領域変動に同期したヒープ領域の配置位置の制御を行う。【選択図】  図１
2005115425.tif 000002
【特許請求の範囲】
【請求項１】
原始プログラムのコンパイルにより生成される中間プログラムを解析し、スタック領域およびヒープ領域からなる動的データ領域を管理する動的データ領域管理情報を生成する動的データ領域管理システムを備える記憶域管理装置であって、
前記中間プログラム中の関数呼び出し命令を検索する関数呼び出し命令検索手段と、
前記検索により関数の呼び出しを検出したときに、前記検出された関数の中で定義されている変数を検索する局所変数検索手段と、
前記関数の中における前記ヒープ領域確保命令の使用を検索するヒープ領域確保命令検索手段と、
前記関数の中における前記ヒープ領域解放命令の使用を検索するヒープ領域解放命令検索手段と、
前記それぞれの検索手段における検索結果を記入して動的データ領域管理情報を生成する動的データ領域管理情報生成手段と
を有することを特徴とする記憶域管理装置。
【請求項２】
前記動的データ領域管理情報を前記スタック領域に格納することを特徴とする請求項１に記載の記憶域管理装置。
【請求項３】
前記動的データ領域管理情報に基づき、前記ヒープ領域の発生位置を示すヒープポインタを前記スタック領域に生成することを特徴とする請求項１または２に記載の記憶域管理装置。
【請求項４】
前記ヒープポインタが、前記スタック領域に隣接する領域に前記ヒープ領域の生成を指示することを特徴とする請求項３に記載の記憶域管理装置。
【請求項５】
前記スタック領域の領域が変動するごとに、前記ヒープポインタが前記ヒープ領域の生成位置を指示することを特徴とする請求項４に記載の記憶域管理装置。
【請求項６】
原始プログラムのコンパイルにより生成される中間プログラムを解析し、スタック領域およびヒープ領域からなる動的データ領域を管理する動的データ領域管理用の情報テーブルを生成する記憶域管理方法であって、
前記中間プログラム中の関数使用開始命令を検索する関数使用開始命令検索ステップと、
前記検索により関数の使用開始を検出したときに、前記関数に関する情報テーブルの作成を開始する情報テーブル作成開始ステップと、
前記関数の中で定義されている変数を検索して変数名を前記情報テーブルに記入する局所変数検索ステップと、
前記関数の中におけるヒープ操作用標準関数の使用を検索するヒープ情報検索ステップと、
前記ヒープ情報検索により前記ヒープ操作用標準関数を検出したときに、ヒープ情報を前記情報テーブルに記入するヒープ情報記入ステップと、
前記関数の中における他の関数の呼び出し命令を検索する他関数呼び出し命令検索ステップと、
前記他関数呼び出し命令検索により他関数の呼び出しを検出したときに、関数呼び出し情報を前記情報テーブルに記入する関数呼び出し情報記入ステップと、
前記関数の使用終了命令を検索する関数使用終了命令検索ステップと、
前記関数使用終了命令検索により関数の使用終了を検出したときに、前記情報テーブルの作成を終了する情報テーブル作成終了ステップとを有し、
前記中間プログラムに記載されている総ての関数使用開始命令の検索を終了するまで前記各ステップの操作を繰り返して前記中間プログラムで使用されている総ての関数のそれぞれに対する前記情報テーブルを作成することを特徴とする記憶域管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、原始プログラムのコンパイルに関し、特に目的プログラムにおける記憶域の管理を行う記憶域管理装置および記憶域管理方法に関する。
【背景技術】
【０００２】
近年、各種の電子機器にマイクロプロセッサとソフトウェアを組み込み、ソフトウェアにより電子機器を制御することが多い。
【０００３】
図８は、このような組み込み用ソフトウェアの開発システムの一般的な例を示している。
【０００４】
ユーザが作成したｎ個の原始プログラム１０１、１０２、・・・、１０ｎは、コンパイラ２００により中間コードプログラム２０１、２０２、・・・、２０ｎに変換された後、アセンブリプログラム３０１、３０２、・・・、３０ｎに変換される。
【０００５】
さらに、リンカ４００により必要に応じてライブラリ５００が参照されて、アセンブリプログラム３０１、３０２、・・・、３０ｎは、１本の実行可能形式の目的プログラム４０１に結合される。
【０００６】
生成された目的プログラムが実行されるときの環境は実行時環境と呼ばれる。原始プログラム中に宣言された変数が、どの記憶域に割り付けられるか、あるいは、その記憶領域が不要になったときに、いつ、どのようにその記憶域が解放されるかは、その実行環境により固有に決定されている。
【０００７】
図９は、従来の記憶域の割り付けの例を示す図である。
【０００８】
記憶域６００は、システム領域６０１、静的データ領域６０２、動的データ領域６０３に大別される。このうち、動的データ領域６０３は、さらに、スタック領域６０３Ａとヒープ領域６０３Ｂに分けられる。
【０００９】
システム領域６０１はＲＯＭで構成され、ここには、マイクロプロセッサの動作に最低限必要な基本プログラムと定常データが格納される。
【００１０】
静的データ領域６０２と動的データ領域６０３はＲＡＭで構成され、ここに、原始プログラム中で宣言された変数が格納される。この変数には、「大域変数」、「局所変数」、「動的変数」などの種類がある。
【００１１】
「大域変数」は、プログラムの総ての実行を通じて記憶域が確保されるものであり、「局所変数」は、関数呼び出しに同期して記憶域が確保され、関数呼び出しの完了時点で消滅するものである。
【００１２】
一方、「動的変数」は、プログラム実行中に命令の指示により任意のサイズの記憶域を確保するものである。
【００１３】
一般に、「大域変数」は静的データ領域６０２に格納され、「局所変数」はスタック領域６０３Ａに格納され、「動的変数」はヒープ領域６０３Ｂに格納される。
【００１４】
このうち、「動的変数」が記憶域を確保する作業は、動的記憶割り当てと呼ばれる。動的記憶割り当てを指示する命令の例として、Ｃ言語におけるライブラリ関数ｍａｌｌｏｃがある。
【００１５】
また、この動的記憶域の確保、解放を高速に行うために、ａｌｌｏｃａ関数を用いる方法も提案されている（例えば、特許文献１参照。）。
【００１６】
しかし、ａｌｌｏｃａ関数はＣ言語の標準関数でないため、一般的には、ａｌｌｏｃａ関数の使用は推奨されていない。
【特許文献１】特開平８−２７２６２１号公報  （第３ページ、図２）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上述したように、動的データ領域６０３は、プログラムの実行中に動的にそのサイズが増減する。しかし、目的プログラムが生成された時点では、どの程度の記憶域が必要となるか不明である。したがって、その中のスタック領域６０３Ａとヒープ領域６０３Ｂがオーバーラップしないように、動的データ領域６０３の両端にスタック領域６０３Ａとヒープ領域６０３Ｂを配置するのが一般的である。
【００１８】
そこで、プログラム作成者は、プログラム作成時にスタック領域６０３Ａとヒープ領域６０３Ｂの最大領域を推定して、予め記憶域６００の中にその領域を確保しておく必要がある。
【００１９】
図１０は、そのために使用するスタートアッププログラムと呼ばれる原始プログラムの例である。
【００２０】
スタートアッププログラム７００において、（７００−１）行目がスタック領域のサイズ、（７００−２）行目と（７００−３）行目がヒープ領域のサイズ等を指定している。
【００２１】
このように、動的データ領域６０３の両端にスタック領域６０３Ａとヒープ領域６０３Ｂを向かい合わせに配置し、サイズを増やす場合は、それぞれ、動的データ領域６０３の中央部に向かって、その領域を拡張する。
【００２２】
しかし、このように配置した場合、動的データ領域６０３の中央部に未使用の空白領域が発生することがある。これは、スタック領域６０３Ａとヒープ領域６０３Ｂのそれぞれに余裕を取って領域を確保するためである。
【００２３】
この空白領域が多すぎることは、記憶域の使用効率が悪いことを意味する。特に、記憶域の容量が限られている組み込み用マイクロプロセッサでは、記憶域の使用効率が悪いことは問題となる。
【００２４】
そこで、本発明の目的は、動的データ領域を使用効率良く管理する記憶域管理装置および記憶域管理方法を提供することにある。
【課題を解決するための手段】
【００２５】
本発明の一態様によれば、原始プログラムのコンパイルにより生成される中間プログラムを解析し、スタック領域およびヒープ領域からなる動的データ領域を管理する動的データ領域管理情報を生成する動的データ領域管理システムを備える記憶域管理装置であって、前記中間プログラム中の関数呼び出し命令を検索する関数呼び出し命令検索手段と、前記検索により関数の呼び出しを検出したときに、前記検出された関数の中で定義されている変数を検索する局所変数検索手段と、前記関数の中における前記ヒープ領域確保命令の使用を検索するヒープ領域確保命令検索手段と、前記関数の中における前記ヒープ領域解放命令の使用を検索するヒープ領域解放命令検索手段と、前記それぞれの検索手段における検索結果を記入して動的データ領域管理情報を生成する動的データ領域管理情報生成手段とを有することを特徴とする記憶域管理装置が提供される。
【００２６】
また、本発明の一態様によれば、原始プログラムのコンパイルにより生成される中間プログラムを解析し、スタック領域およびヒープ領域からなる動的データ領域を管理する動的データ領域管理用の情報テーブルを生成する記憶域管理方法であって、前記中間プログラム中の関数使用開始命令を検索する関数使用開始命令検索ステップと、前記検索により関数の使用開始を検出したときに、前記関数に関する情報テーブルの作成を開始する情報テーブル作成開始ステップと、前記関数の中で定義されている変数を検索して変数名を前記情報テーブルに記入する局所変数検索ステップと、前記関数の中におけるヒープ操作用標準関数の使用を検索するヒープ情報検索ステップと、前記ヒープ情報検索により前記ヒープ操作用標準関数を検出したときに、ヒープ情報を前記情報テーブルに記入するヒープ情報記入ステップと、前記関数の中における他の関数の呼び出し命令を検索する他関数呼び出し命令検索ステップと、前記他関数呼び出し命令検索により他関数の呼び出しを検出したときに、関数呼び出し情報を前記情報テーブルに記入する関数呼び出し情報記入ステップと、前記関数の使用終了命令を検索する関数使用終了命令検索ステップと、前記関数使用終了命令検索により関数の使用終了を検出したときに、前記情報テーブルの作成を終了する情報テーブル作成終了ステップとを有し、前記中間プログラムに記載されている総ての関数使用開始命令の検索を終了するまで前記各ステップの操作を繰り返して前記中間プログラムで使用されている総ての関数のそれぞれに対する前記情報テーブルを作成することを特徴とする記憶域管理方法が提供される。
【発明の効果】
【００２７】
本発明の記憶域管理装置および記憶域管理方法によれば、スタック領域に隣接してヒープ領域が生成されるので、スタック領域とヒープ領域の間に無用な空白領域が生じることを防止することができる。これにより、記憶域の使用効率を向上させることができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施例を図面を参照して説明する。
【実施例】
【００２９】
図１は、本発明の実施例に係る記憶域管理装置の構成を示すブロック図である。
【００３０】
動的データ領域管理システム１は、中間プログラム２を読み込んで解析し、その中に含まれる動的データ領域の管理に関する情報を抽出して動的データ領域管理情報３を生成するシステムである。
【００３１】
この動的データ領域管理システム１は、中間プログラム２の中に関数呼び出し命令が存在するかどうかを検索する関数呼び出し命令検索手段１１と、関数呼び出し命令が存在した場合に、その関数の中で定義されている局所変数を検索する局所変数検索手段１２と、さらに、その関数の中で、ヒープ領域確保命令が使用されているかどうかを検索するヒープ領域確保命令検索手段１３と、ヒープ領域解放命令が使用されているかどうかを検索するヒープ領域解放命令検索手段１４、および上記各検索手段の検索結果に基づいて動的データ領域の管理に関する情報を生成する動的データ領域管理情報生成手段１５から構成される。
【００３２】
図２は、上記動的データ領域管理システム１の処理フローを示すフローチャートである。
【００３３】
中間プログラムが読み込まれると、先ず、関数呼び出し命令の使用を検索するため、＜ＢＥＧＩＮ，ｆｕｎｃ＞で始まる文字列を検索する（ステップＳ１）。
【００３４】
＜ＢＥＧＩＮ，ｆｕｎｃ＞で始まる文字列が検出されると、この関数についての情報を記入するための情報テーブルを用意する（ステップＳ２）。
【００３５】
次に、文字列＜Ｉ＞で始まる局所変数を検索し、検出された局所変数をステップＳ２で用意した情報テーブルに記入する（ステップＳ３）。
【００３６】
さらに、ヒープ操作用標準関数が使用されているかどうか検索する。具体的には、ヒープ領域用の記憶域を確保するための関数＜ｍａｌｌｏｃ＞と、ヒープ領域用に確保した記憶域を解放するための関数＜ｆｒｅｅ＞を検索する（ステップＳ４）。
【００３７】
ヒープ操作用標準関数が検出されたら、このヒープに関する情報をステップＳ２で用意した情報テーブルに記入する（ステップＳ５）。
【００３８】
次に、この関数の中で、他の関数の呼び出しがあるかどうかを検索するため、＜ｆｕｎｃ＞で始まる文字列を検索する（ステップＳ６）。
【００３９】
なお、ステップＳ４で、ヒープ操作用標準関数が検出されなかった場合も、ステップＳ６へ進む。
【００４０】
ステップＳ６で、他の関数の呼び出しが検出されたら、この関数呼び出し情報をステップＳ２で用意した情報テーブルに記入する（ステップＳ７）。
【００４１】
その後、この関数に関するプログラム記述の終了点を検索するため、＜ＥＮＤ，ｆｕｎｃ＞で始まる文字列を検索する（ステップＳ８）。
【００４２】
なお、ステップＳ６で、ヒープ操作用標準関数が検出されなかった場合も、ステップＳ８へ進む。
【００４３】
そして、＜ＥＮＤ，ｆｕｎｃ＞で始まる文字列が検出された時点で、この関数についての情報テーブルの作成が終了する（ステップＳ９）。
【００４４】
この後，次の関数呼び出し命令の使用を検索するため，ステップＳ１へ戻る。以降、上述のステップＳ１〜ステップＳ９の処理を繰り返し，中間プログラムに記述されている総ての関数それぞれに情報テーブルを作成する。
【００４５】
総ての関数に対する情報テーブルの作成が終了し，ステップＳ１で＜ＢＥＧＩＮ，ｆｕｎｃ＞で始まる文字列が検出されなくなったら、本フローによる処理は終了する。
【００４６】
図３〜図６を用いて、この処理フローによって作成される情報テーブルの例を示す。
【００４７】
図３は、Ｃ言語で記述された原始プログラムの例である。
【００４８】
原始プログラム１０では、４つの関数ｆｕｎｃ１〜ｆｕｎｃ４が使用され、このうち２つの関数ｆｕｎｃ１とｆｕｎｃ２でヒープ操作用標準関数ｍａｌｌｏｃとｆｒｅｅが使用されている。
【００４９】
図４は、原始プログラムをコンパイルすることによって得られる中間プログラムの例である。
【００５０】
中間プラグラム２０は、図３の原始プログラム１０をコンパイルして得られる中間プログラムの例であるが、ここでは、図２の処理フローの説明に関わる部分のみを抜き出して記載している。
【００５１】
ここで、（２０−１）の＜ＢＥＧＩＮ，ｆｕｎｃ１＞が関数ｆｕｎｃ１の呼び出し命令、（２０−２）が局所変数Ｉ１、Ｉ２、Ｉ３の定義、（２０−３）が標準関数ｍａｌｌｏｃの呼び出し命令、（２０−４）が他の関数ｆｕｎｃ２の呼び出し命令、（２０−５）が標準関数ｆｒｅｅの呼び出し命令であり、（２０−６）の＜ＥＮＤ，ｆｕｎｃ１＞が関数ｆｕｎｃ１に関するプログラム記述の終了を表わす。
【００５２】
図５は、図２に示す処理フローにより中間プログラム２０を処理した結果得られる情報テーブルの例を示す図である。
【００５３】
動的データ領域管理情報３０に含まれる情報テーブル３０Ａ〜３０Ｄは、それぞれ関数ｆｕｎｃ１〜ｆｕｎｃ４に対応しており、それぞれの情報テーブルには、関数名、局所変数情報、ヒープ情報、関数呼び出し情報が記入されている。
【００５４】
例えば、情報テーブル３０Ａには、関数名としてｆｕｎｃ１が記されており、局所変数情報として３つの変数Ｉ１、Ｉ２、Ｉ３に関する情報が記入されている。また、関数ｆｕｎｃ１では、標準関数ｍａｌｌｏｃおよびｆｒｅｅが使用されているため、ヒープ情報が記入されている。さらに、他の関数の呼び出しも行われているため、関数呼び出し情報も記入されている。
【００５５】
同様に、関数ｆｕｎｃ２の情報テーブル３０Ｂにも、関数名、局所変数情報、ヒープ情報、関数呼び出し情報が記入されている。
【００５６】
一方、標準関数ｍａｌｌｏｃおよびｆｒｅｅを使用せず、他の関数の呼び出しも行わない関数ｆｕｎｃ３、ｆｕｎｃ４の情報テーブル３０Ｃ、３０Ｄには、ヒープ情報と関数呼び出し情報に関する情報が記入されていない。
【００５７】
次に、上述の情報テーブルに基づく動的データ領域の管理について説明する。
【００５８】
図６は、本実施例における動的データ領域の割り付けの例を示す図である。
【００５９】
動的データ領域６０は、スタック領域６１とヒープ領域６２から構成されるが、上述の情報テーブルに記入されている局所変数などの情報は総てスタック領域６１に格納される。ただし、情報テーブルに記入されているヒープ情報は、ヒープの発生位置とヒープ領域幅を示すヒープポインタ（ｈｅａｐ＿ｐｔｒ）として格納される。
【００６０】
このとき、ヒープポインタに記されるヒープの発生位置は、スタック領域６１に隣接するアドレスが指定される。
【００６１】
そのため、従来の動的データ領域の割り付けと異なり、本実施例においては、スタック領域６１とヒープ領域６２に間には空白域が生じない。
【００６２】
ただし、スタック領域６１へのスタックの割り当てと解放は、関数の呼び出しの都度行われるので、これに同期してヒープポインタも書き直し、ヒープ領域６２の再配置を行う。
【００６３】
図７は、プログラムの実行に伴い、動的データ領域６０の状態が変化する様子の例を示す図である。
【００６４】
ここでは、図３に示す原始プログラム１０を例にとり、関数の呼び出しに応じて、スタック領域６１とヒープ領域６２が変動する様子を示す。
【００６５】
図７（ａ）は、関数ｆｕｎｃ１が呼び出され、局所変数とｍａｌｌｏｃ関数が読み込まれたときのスタック領域６１とヒープ領域６２の様子を示す。このとき、スタック領域６１には、局所変数ａ１１、ａ１２、ａ１３とヒープポインタ（ｈｅａｐ＿ｐｔｒ  Ｃ１）が格納され、ヒープ領域６２には、ヒープポインタ（ｈｅａｐ＿ｐｔｒ  Ｃ１）の指示に従い、ヒープ（ｈｅａｐ  Ｃ１）が、スタック領域６１に隣接して配置される。
【００６６】
図７（ｂ）は、関数ｆｕｎｃ２が呼び出され、関数ｆｕｎｃ２における局所変数の読み込みとｍａｌｌｏｃ関数の読み込みまで、プログラムの実行が進んだときのスタック領域６１とヒープ領域６２の様子を示す。
【００６７】
このとき、スタック領域６１には、図７（ａ）の状態に、さらに、局所変数ａ２１、ａ２２とヒープポインタ（ｈｅａｐ＿ｐｔｒ  Ｃ２）が格納される。
【００６８】
スタック領域６１の変動に応じてｈｅａｐ  Ｃ１が再配置されるとともに、
ヒープポインタ（ｈｅａｐ＿ｐｔｒ  Ｃ２）の指示に従い、ｈｅａｐ  Ｃ２が、ｈｅａｐ  Ｃ１に隣接して配置される。
【００６９】
図７（ｃ）は、さらにプログラムの実行が進み、関数ｆｕｎｃ３、ｆｕｎｃ４が呼び出されたときのスタック領域６１とヒープ領域６２の様子を示す。
【００７０】
このとき、スタック領域６１には、図７（ｂ）の状態に、さらに、局所変数ａ３１、ａ３２とａ４１、ａ４２が格納される。このスタック領域６１の変動に応じて、ｈｅａｐ  Ｃ１とｈｅａｐ  Ｃ２は再配置される。
【００７１】
図７（ｄ）は、さらにプログラムの実行が進んで、関数ｆｕｎｃ３、ｆｕｎｃ４および関数ｆｕｎｃ２の実行が終わり、さらにｈｅａｐ  Ｃ１も解放されたときの状態を示す。
【００７２】
このとき、動的データ領域６０には、スタック領域６１のみが存在する。
【００７３】
このような本実施例によれば、スタック領域６１の領域が変動したときに、その変動に応じて、ヒープ領域６２がスタック領域６１に隣接する位置に再配置される。そのため、スタック領域６１とヒープ領域６２の間に空白領域が生じることを防止できる。
【図面の簡単な説明】
【００７４】
【図１】本発明の実施例に係る記憶域管理装置の構成を示すブロック図。
【図２】本発明の実施例に係る記憶域管理方法のフローチャート。
【図３】原始プログラムの一例を示す図。
【図４】中間プログラムの一例を示す図。
【図５】本発明の実施例に係る動的データ領域管理情報の一例を示す図。
【図６】本発明の実施例に係る動的データ領域の割り付けの例を示す図。
【図７】本発明の実施例に係る動的データ領域の状態の変化の例を示す図。
【図８】組み込み用ソフトウェアの開発システムの一般的な例を示す図。
【図９】従来の記憶域の割り付けの例を示す図。
【図１０】スタートアッププログラムの一例を示す図。
【符号の説明】
【００７５】
１  動的データ領域管理システム
１０  原始プログラム
１１  関数呼び出し検索手段
１２  局所変数検索手段
１３  ヒープ領域確保命令検索手段
１４  ヒープ領域解放命令検索手段
１５  動的データ領域管理情報生成手段
２、２０  中間プログラム
３、３０  動的データ領域管理情報
３０Ａ、３０Ｂ、３０Ｃ、３０Ｄ  情報テーブル
６００  記憶域
６０１  システム領域
６０２  静的データ領域
６０、６０３  動的データ領域
６１、６０３Ａ  スタック領域
６２、６０３Ｂ  ヒープ領域
７００  スタートアッププログラム
【図１】
2005115425.tif 000003
【図２】
2005115425.tif 000004
【図３】
2005115425.tif 000005
【図４】
2005115425.tif 000006
【図５】
2005115425.tif 000007
【図６】
2005115425.tif 000008
【図７】
2005115425.tif 000009
【図８】
2005115425.tif 000010
【図９】
2005115425.tif 000011
【図１０】
2005115425.tif 000012