JPH09330232A

JPH09330232A - 動的記憶域割り付け方式

Info

Publication number: JPH09330232A
Application number: JP8168634A
Authority: JP
Inventors: Junichi Shibuya; 純一渋谷
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1996-06-07
Filing date: 1996-06-07
Publication date: 1997-12-22

Abstract

(57)【要約】【課題】動的な記憶域の確保・解放の為の記憶域管理ラ
イブラリの呼出しを削減させることによりライブラリ呼
出し及び動的記憶域管理機構によるオーバヘッドを減少
させる。【解決手段】確保する記憶域のサイズがプログラム翻訳
時に判明する動的な記憶域の確保要求を検出し確保要求
に対し返却された記憶域を識別するポインタ値に関する
データフローとプログラムの制御フローを解析し確保さ
れた記憶域の生存区間を検出する生存区間検出手段と検
出された複数の動的記憶域の生存区間の重複を検査する
生存区間重複検査手段と生存区間重複検査手段により判
明した生存区間の重複状況を考慮して同一の記憶域を共
有可能な一つ以上の動的記憶域をグループ化する手段と
同一グループに属する動的記憶域の確保・解放の要求を
無効としグループの先頭で確保された記憶域を共有して
利用するようプログラムを変更する手段を備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、情報処理装置の言
語処理系に関し、特に言語処理系の動的記憶域割り付け
方式に関する。

【０００２】

【従来の技術】この種の従来技術として、例えば特開昭
６３−２２６７５０号公報には、動的な記憶域の割り付
けに際して、指定したメモリ容量の割当てが受けられな
い時に、割当て可能な最大のメモリ容量を２分探索法を
用いて求め、再割当てを受けて、大容量のメモリを確保
することによって処理の迅速化を図るようにした動的メ
モリ確保方式が提案されている。

【０００３】そして、上記公報以外の従来技術において
も、動的記憶域の割り付けの処理効率を改善する方式と
して、プログラムからの記憶域割り付け要求に対する処
理方式を改善するアプローチのみにとどまっているとい
うのが実状である。

【０００４】

【発明が解決しようとする課題】すなわち、従来の動的
記憶域の割り付け方式においては、記憶域の確保・解放
の処理方式の改善により、動的記憶域の割り付けの高速
化を図っているが、動的記憶域を多用するプログラムに
おいては、十分な処理の高速化が実現されない場合が少
なくない。この理由を以下に説明する。

【０００５】プログラムから動的な記憶域の割り付け機
能を有するプログラミング言語においては、利用者プロ
グラム（ユーザプログラム）中に記述された動的な記憶
域の確保・解放の指定の記述を、言語処理系が提供する
記憶域管理用のライブラリ関数呼出しに置き換えて実現
している。

【０００６】また、当該の記憶域管理用のライブラリ関
数においては、ランダムな記憶域の確保・解放要求に対
応するため、および記憶域の有効活用のために、一般に
複雑な記憶域管理機構を採用している。

【０００７】従来技術においては、このライブラリ関数
内で実行される複雑な記憶域管理機構の改善することに
より、記憶域の確保・解放の高速化を図ろうとしたもの
であるが、プログラム中に記述された動的記憶域の確保
・解放の要求毎にライブラリ関数の呼出しは依然として
行われるため、ライブラリ関数呼出しによるオーバヘッ
ドの改善には至っていない。

【０００８】特に動的記憶域が多用されるプログラムで
は、ライブラリ関数の呼出しが多数発生し、従来技術に
よる高速化のみでは十分な効果が得られない場合が少な
くない。

【０００９】従って、本発明は、上記事情に鑑みてなさ
れたものであって、その目的は、動的な記憶域の確保・
解放のための記憶域管理ライブラリの呼び出しを削減す
ることによってライブラリ呼び出し及び動的記憶管理機
構によるオーバヘッドを低減し、高速化を達成するよう
にした動的記憶割付方式を提供することにある。

【００１０】

【課題を解決するための手段】前記目的を達成するた
め、本発明の動的記憶域割り付け方式は、ソース・プロ
グラムを解析し該プログラム中で発行される動的な記憶
域の確保・解放要求に関するデータフロー情報、及び該
プログラムの制御フロー情報に基づき、複数の動的な記
憶域間での生存区間の重複状況を検出し、共有可能な複
数の記憶域を検出して共有させることにより、動的な記
憶域の確保・解放のための記憶域管理用のライブラリ呼
出しを削減するように前記ソース・プログラムを自動修
正する手段を備えたことを特徴とする。

【００１１】本発明は、利用者がプログラム中に任意に
記述した動的な記憶域の確保・解放の要求を静的に解析
可能な範囲で、異なる動的な記憶域に対して、共有可能
な複数の記憶域を検出して共有させることにより、動的
な記憶域の確保・解放のための記憶域管理用のライブラ
リ呼出しを削減し、記憶域管理用ライブラリによるオー
バヘッドを減少させるようにしたものである。

【００１２】すなわち、本発明に係る動的記憶域割付方
式は、プログラムの実行中に動的に記憶域を確保・解放
する機能を有するプログラミング言語に対する言語処理
系において、確保する記憶域のサイズがプログラムの翻
訳時に判明する動的な記憶域の確保要求を検出し、当該
の確保要求に対して返却された記憶域を識別するポイン
タ値に関するデータフローとプログラムの制御フローを
解析して当該のポインタ値が識別する記憶域に対する確
保要求から最も離れた位置の解放要求を検出することに
よって確保された記憶域の生存区間を検出する生存区間
検出手段と、生存区間検出手段によって検出された複数
の動的記憶域の生存区間の重複を検査する生存区間重複
検査手段と、生存区間重複検査手段によって判明した生
存区間の重複状況を考慮して同一の記憶域を共有可能な
一つ以上の動的記憶域をグループ化するグループ化手段
と、一つのグループ中の動的記憶域の内で最も大きいサ
イズの記憶域を当該のグループ中でその生存区間が最も
早く開始される動的記憶域の生存区間の先頭で確保し当
該のグループ中でその生存区間が最も遅く終了する動的
記憶域の生存区間の最後で解放し同一グループに属する
動的記憶域の確保・解放の要求を無効としてグループの
先頭で確保された記憶域を共有して利用するようにプロ
グラムを変更するプログラム変更手段を有することを特
徴とする。

【００１３】

【発明の実施の形態】本発明の実施形態について図面を
参照して以下に詳細に説明する。図１は、本発明の実施
の形態の構成をブロック図にて示したものである。

【００１４】図１を参照すると、本発明の実施の形態
は、言語処理系１、生存区間検出手段２、生存区間重複
検出手段３、グループ化手段４、プログラム変更手段
５、ソースプログラム６、データフロー情報７、制御フ
ロー情報８、生存区間情報９、生存区間重複状況情報１
０、及びグループ情報１１を備えて構成される。以下各
要素を説明する。

【００１５】図２は、本発明の実施の形態におけるデー
タフロー情報７の構成の一例を示す図である。

【００１６】図２を参照すると、データフロー情報７
は、データフローテーブルならびにアリアステーブルに
よって構成される。データフローテーブルは、各エント
リが、データ、データに値が設定される位置、当該の値
を保持している範囲が終了する位置、及びアリアステー
ブルへのチェイン（ポインタ）と、を備えて構成され
る、データフロー情報の集合である。また、アリアステ
ーブルは、データフローテーブルの各エントリに対応し
て作成され、対応するデータフローテーブルのエントリ
に格納されているデータフロー情報によって識別される
データが保持する値の写しを保持するアリアステーブル
の設定位置、終了位置によって構成されるアリアス情報
の集合である。

【００１７】上記したデータフロー情報７は、言語処理
系１によって事前に作成されているものとする。

【００１８】図３は、本発明の実施の形態における、制
御フロー情報８の構成の一例を示す図である。図３を参
照すると、制御フロー情報８は、基本ブロックに関する
情報を保持する１又は複数の基本ブロック情報によって
構成され、各基本ブロックは基本ブロック間の制御フロ
ーに従ってチェインによって結ばれている。

【００１９】基本ブロック情報は、基本ブロックの開始
位置、終了位置、当該の基本ブロックから制御が移行す
る１つ以上の他の基本ブロックに対する基本ブロック情
報へのチェインによって構成される。制御フロー情報８
は、言語処理系１によって事前に作成されているものと
する。

【００２０】図４は、本発明の実施の形態における生存
区間情報９の構成の一例を示す図である。図４を参照す
ると、生存区間情報９は、生存区間テーブルと、解放情
報テーブルと、から構成される。生存区間テーブルは、
ソースプログラム６中で確保される動的な記憶域に関す
る情報の集合であり、各エントリ（＃１〜＃ｎ）は、動
的な記憶域が生存する区間の区間開始情報、区間終了情
報、動的な記憶域を識別するポインタ値を保持するデー
タ、動的な記憶域のサイズ、当該の動的な記憶域に対応
する解放情報テーブルへのチェインと、を備えて構成さ
れる。そして、図示のように、区間開始情報は、区間の
開始位置と開始位置が含まれる基本ブロック番号を保持
し、区間終了情報は、区間の終了位置と終了位置が含ま
れる基本ブロック番号を保持する。また、解放情報テー
ブル１〜ｎは、対応する動的な記憶域の解放情報の集合
であり、解放情報は、動的な記憶域の解放位置と解放位
置が含まれる基本ブロック番号を保持する。

【００２１】図５は、本発明の実施の形態における、生
存区間重複状況情報１０の構成の一例を示す図である。
図５を参照すると、生存区間重複状況情報１０は、動的
な記憶域と他の動的な記憶域との生存区間の重複情報を
表す２次元のビット配列からなり、各次元の要素数は共
に生存区間情報９の生存区間テーブルのエントリ数と同
一とされる（行及び列方向に＃１〜＃ｎ）。生存区間重
複状況情報１０の各ビットは、該当する動的な記憶域同
士の生存区間が重複する場合には「１」が設定され、そ
れ以外の場合は「０」が設定される。

【００２２】図６は、本発明の実施の形態におけるグル
ープ情報１１の構成の一例を示す図である。図６を参照
すると、グループ情報１１は、グループ化された動的な
記憶域に対するグループ開始位置、グループ終了位置、
生成データ、サイズによって構成されるエントリの集合
である。

【００２３】次に、本発明の実施形態の動作について図
１を参照して説明する。

【００２４】言語処理系１は、ソースプログラム６を入
力して、データフロー情報７、制御フロー情報８を生成
する。

【００２５】次に、言語処理系１は、生存区間検出手段
２、生存区間重複検出手段３、グループ化手段４、プロ
グラム変更手段５を順次起動して、ソースプログラム６
中の動的な記憶域の確保・解放のための記憶域管理用ラ
イブラリ関数の呼出しが削減されるようにソースプログ
ラム６を変更する。

【００２６】生存区間検出手段２は、ソースプログラム
６、データフロー情報７、制御フロー情報８を入力し
て、ソースプログラム６中の確保する記憶域のサイズが
静的に判明する動的な記憶域の確保要求によって確保さ
れる動的な記憶域が、確保された位置から最も離れた位
置で解放されるまでの区間（生存区間）を下記の手順で
検出する。

【００２７】（１）ソースプログラム６を調査し、確保
する記憶域のサイズが静的に判明する動的な記憶域の確
保要求の位置、サイズ、および、その確保要求によって
確保された動的な記憶域を識別するポインタ値を保持す
るデータを検出し、生存区間情報９の生存区間テーブル
の区間開始情報の位置フィールド、生存区間テーブルの
サイズフィールド、生存区間テーブルのデータフィール
ドに格納する。

【００２８】この処理によって、生存区間情報９には、
ソースプログラム６中の確保する記憶域のサイズが静的
に判明する全ての動的な記憶域に対する確保要求の位
置、サイズ、ならびに確保された動的な記憶域を識別す
るポインタ値を保持するデータに関する情報が格納され
る。

【００２９】（２）次に、ソースプログラム６を調査
し、各動的な記憶域を識別するポインタ値を保持するデ
ータおよびそのアリアスデータが、当該動的な記憶域を
識別するポインタ値を保持している範囲内の、当該動的
な記憶域の解放要求の位置を全て検出して、生存区間情
報９中に、当該動的な記憶域に対応する解放情報テーブ
ル（図４参照）を作成し、その各エントリの解放情報の
位置フィールドに検出した解放要求の位置を格納する。

【００３０】この処理において、各動的な記憶域を識別
するポインタ値を保持するデータと、そのアリアスデー
タがその値を保持している範囲を取得するために生存区
間情報９の生存区間テーブルの各エントリのデータフィ
ールドに対応するデータフロー情報７のデータフローテ
ーブルのデータフロー情報の設定位置フィールド・終了
位置フィールド、および対応するアリアステーブルの各
アリアス情報の設定位置フィールド・終了位置フィール
ドが参照される。

【００３１】（３）続いて、制御フロー情報８の各基本
ブロック情報の開始位置フィールド・終了位置フィール
ドを参照して、生存区間情報９の生存区間テーブルの区
間開始情報の位置フィールド、解放情報テーブルの解放
情報の位置フィールドに格納されている位置に対応する
基本ブロック番号を決定し、生存区間情報９の生存区間
テーブルにおける、区間開始情報のブロックフィール
ド、解放情報テーブルの解放情報のブロックフィールド
に、基本ブロック番号を設定する。

【００３２】（４）最後に、生存区間情報９の解放情報
テーブル、制御フロー情報８を参照して、各々の動的な
記憶域に対するいかなる解放要求経由で処理が移行して
も、必ず通過する確保要求から最も離れた基本ブロック
を決定する。この基本ブロックの先頭の位置と基本ブロ
ック番号を、生存区間情報９の生存区間テーブルの区間
終了情報の位置フィールド・ブロックフィールドに格納
する。解放要求が１つの場合には、その解放の位置が生
存区間の終わりとなる。

【００３３】いかなる解放要求経由で処理が移行して
も、必ず通過する基本ブロックが存在しない場合には、
当該動的な記憶域は、この処理の対象外とし、既に生存
区間情報９に格納された情報を削除する。

【００３４】生存区間重複検出手段３は、生存区間検出
手段２によって生成された、生存区間情報９中の各動的
な記憶域に対する、区間開始情報及び区間終了情報、を
参照して、各動的な記憶域と、生存区間が重複する動的
な記憶域を検出し、生存区間重複状況情報１０（図５参
照）を設定する。

【００３５】グループ化手段４は、生存区間重複検出手
段３によって作成された生存区間重複状況情報１０を参
照して、生存区間が重複しない動的な記憶域群をグルー
プ化して、グループ情報１１（図６参照）を生成する。

【００３６】グループ情報１１のグループ開始位置は、
生存区間情報９の生存区間テーブル中の、グループ化さ
れた動的な記憶域群の内の最も早く出現するものに対応
するエントリの区間開始情報の位置フィールドの値が設
定される。また、グループ情報１１のグループ終了位置
は、生存区間情報９の生存区間テーブル中の、グループ
化された動的な記憶域群の内の最も最後に出現するもの
に対応するエントリの区間終了情報の位置フィールドの
値が設定される。グループ情報１１のサイズは、生存区
間情報９の生存区間テーブル中の、グループ化された動
的な記憶域群の内の最もサイズが大きいものに対応する
エントリのサイズフィールドの値が設定される。

【００３７】プログラム変更手段５は、グループ化手段
４によって作成されたグループ情報１１の各エントリを
参照してソースプログラム６を下記の手順で変更する。

【００３８】（１）グループ情報１１のグループ開始位
置に、グループ情報１１のサイズフィールドの値による
動的な記憶域の確保要求を追加する。

【００３９】（２）当該動的な記憶域の確保要求によっ
て確保された動的な記憶域を識別するポインタ値を保持
するためのポインタデータを生成し、当該生成データに
確保された動的な記憶域を識別するポインタ値が格納さ
れるようにする。また、生成データ名をグループ情報１
１の生成データフィールド（図６参照）に設定する。

【００４０】（３）当該グループに属する全ての動的な
記憶域に対する確保要求を、当該の確要求によって確保
された動的な記憶域を識別するポインタ値を保持するポ
インタデータに、上記した生成データが保持する値を代
入する処理に変更する。

【００４１】（４）当該グループに属する全ての動的な
記憶域に対する全ての解放要求を削除する。

【００４２】（５）グループ情報１１のグループ終了位
置に、当該動的な記憶域の解放要求を追加する。解放さ
れる動的な記憶域を識別するポインタ値は、グループ情
報１１の生成データフィールドに設定されている生成デ
ータに保持されている。

【００４３】以上により、本発明の実施の形態による動
的記憶域の割り付け方式の処理が完了し、ソースプログ
ラム６中の動的な記憶域の確保・解放のための記憶域管
理用ライブラリ関数の呼出しが削減されたソースプログ
ラム６が生成される。

【００４４】

【実施例】次に、上記した本発明の実施の形態をより具
体的に説明すべく、本発明の実施例について図面を参照
して詳細に説明する。本発明の実施例の構成は、前記実
施の形態と同様な構成とされ、図１を参照とすると、言
語処理系１、生存区間検出手段２、生存区間重複検出手
段３、グループ化手段４、プログラム変更手段５、ソー
スプログラム６、データフロー情報７、制御フロー情報
８、生存区間情報９、生存区間重複状況情報１０、グル
ープ情報１１から構成される。

【００４５】図７は、本実施例におけるソースプログラ
ム６の一例を示す図である。図７に示すように、ソース
プログラム６はＰＬ／Ｉ言語によって記述されている。
ソースプログラム中の各行の位置はソースプログラムの
左側に示してある。また、ＰＬ／Ｉ言語における動的な
記憶域の確保要求は、「ＡＬＬＯＣＡＴＥ文」、解放要
求は「ＦＲＥＥ文」によって記述される。これら「ＡＬ
ＬＯＣＡＴＥ文」、「ＦＲＥＥ文」による動的な記憶域
の確保・解放は、言語処理系によって生成された目的プ
ログラムにおいては、動的な記憶域の確保・解放のため
の記憶域管理ライブラリ関数によって実現されている
（リンク手段によってリンクされ実行モジュールが生成
される）。ちなみに、図７に示すソースプログラム６に
おいて、位置１１では「ＡＬＬＯＣＡＴＥ文」によりサ
イズ１２８（次元１２８の文字型配列）の記憶域の確保
要求＃１が発行され（Ｐ１はポインタ型の変数）、位置
３６で「ＦＲＥＥ文」により確保要求＃１の解放要求が
なされている。

【００４６】図８は、本実施例におけるデータフロー情
報７の一具体例（図７に示すプログラムの記憶域確保・
解放に対応）を示す図である。図８を参照して、各フィ
ールドの意味は、前記実施の形態で参照した図２と同一
とされている。例えばデータフロー情報の第１エントリ
の各フィールドの、Ｐ１、１１、３６はそれぞれデー
タ、設定位置、終了位置を示している。

【００４７】図９は、本実施例における制御フロー情報
８の一具体例を示す図である。各フィールドの意味は前
記実施の形態で参照した図３と同様とされており、その
説明は省略する。

【００４８】図１０は、本実施例における生存区間情報
９の一具体例を示す図である。各フィールドの意味は前
記実施の形態で参照した図４と同様とされており、その
説明は省略する。

【００４９】図１１は、本実施例における生存区間重複
状況情報１０の具体例である。各ボットフラグの意味は
前記実施の形態で参照した図２と同様とされている。例
えば動的記憶域＃１は動的記憶域＃２、＃３と生存区間
が重複している。

【００５０】図１２は、本実施例におけるグループ情報
１１の具体例である。各フィールドの意味は前記実施の
形態で参照した図６と同様とされており、その説明は省
略する。

【００５１】図１３は、本実施例における動的記憶域割
り付け方式によって変更されたソースプログラム６の具
体例である。ソースプログラム中の各行の位置はソース
プログラムの左側に示してある。

【００５２】図７に示した元ソースプログラムに対して
追加又は変更された行の位置は、ｎ−ｍの形式で、図７
の同じ行と区別して示してある。図７のソースプログラ
ムにおいて、図１３に存在しない行は、削除された行で
ある。

【００５３】言語処理系１は、ソースプログラム６（図
７参照）を解析して、データフロー情報７（図８参
照）、制御フロー情報８（図９参照）を生成する。

【００５４】本実施例のデータフロー情報７は、データ
Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５に関して、ソースプログ
ラム６（図７参照）上の動的な記憶域を識別するポイン
タ値が設定された位置、ポインタ値が解放要求によって
無効となることによって、当該データに保持されている
値の寿命が終了する位置が、データフローテーブルに設
定される（図８参照）。

【００５５】更に、データフローテーブルの各エントリ
に対応するデータが保持する値の写しを保持するアリア
スデータに関して、ソースプログラム６（図７参照）上
の当該の値が設定された位置、ポインタ値が解放要求に
よって無効となることによって当該データに保持されて
いる値の寿命が終了する位置がアリアステーブルに設定
される。

【００５６】本実施例では、アリアステーブルは、図７
の位置４５においてデータＰ３が保持するポインタ値を
代入されているデータＰ６（Ｐ６＝Ｐ３）に関するもの
のみである。

【００５７】本実施例の制御フロー情報８は、図９を参
照すると、基本ブロック情報＃１、＃２、＃３、＃４、
＃５、＃６、＃７、＃８、＃９によって構成され、各基
本ブロック情報は、ソースプログラム６上の開始位置、
終了位置、当該制御ブロックから制御が移行される他の
基本ブロックへのチェインを保持している。

【００５８】言語処理系１は、続いて、生存区間検出手
段２、生存区間重複検出手段３、グループ手段４、プロ
グラム変更手段５を順次起動して、ソースプログラム６
（図７参照）中の動的な記憶域の確保・解放のための記
憶域管理用ライブラリ関数の呼出しが削減されるように
変更されたソースプログラム６（図１３参照）を生成す
る。

【００５９】生存区間検出手段２は、ソースプログラム
６（図７参照）を調査して、「ＡＬＬＯＣＡＴＥ文」の
出現位置（１１、１５、１９、２５、３７）と、各「Ａ
ＬＬＯＣＡＴＥ文」で確保された動的な記憶域のサイズ
（１２８、２５６、３００、２５６、１００）、確保さ
れた動的な記憶域を識別するポインタ値を保持するデー
タ（Ｐ１、Ｐ２、Ｐ４、Ｐ５、Ｐ３）を生存区間情報９
（図１０参照）の生存区間テーブルの区間開始情報の位
置フィールド、サイズフィールド、データフィールドに
設定する。

【００６０】次に、生存区間情報９（図１０参照）の生
存区間テーブルのエントリ＃１、＃２、＃３、＃４、＃
５のそれぞれに対して、ソースプログラム６（図７参
照）を調査して、各エントリに対応する動的な記憶域に
対する「ＦＲＥＥ文」の出現位置（３６、１８、２２、
２８、３４、４１、４８）を検出し、生存区間情報９
（図１０参照）の生存区間テーブルの対応するエントリ
配下の解放情報テーブルの解放情報の位置フィールドに
設定する。

【００６１】「ＦＲＥＥ文」の検出に際しては、データ
フロー情報７（図８参照）を参照して、データＰ１、Ｐ
２、Ｐ４、Ｐ５、Ｐ３、及びＰ３の転写データＰ６に該
当する動的な記憶域を識別するポインタ値が保持されて
いる範囲を調査する。

【００６２】続いて、制御フロー情報８（図９参照）を
参照して、生存区間情報９（図１０参照）中の生存区間
テーブルの区間開始情報の位置フィールドに設定されて
いる位置（１１、１５、１９、２５、３７）が属する基
本ブロック番号（＃１、＃２、＃２、＃３、＃６）を決
定し、同じ区間開始情報のブロックフィールドに設定す
る。また、生存区間情報９（図１０参照）中の解放情報
テーブルの解放情報の位置フィールドに設定されている
位置（３６、１８、２２、２８、３４、４１、４８）が
属する基本ブロック番号（＃６、＃２、＃２、＃４、＃
５、＃７、＃８）を同じ解放情報のブロックフィールド
に設定する。

【００６３】基本ブロック番号の決定は、制御フロー情
報８（図９参照）中の各基本ブロック情報の開始位置フ
ィールドと終了位置フィールドに保持されている値の間
に属するか否かで行われる。

【００６４】最後に、各動的な記憶域の生存区間の区間
終了位置と属する基本ブロックを決定するために、生存
区間情報９（図１０参照）中の生存区間テーブルの各エ
ントリに対応する解放情報テーブルのいかなる解放要求
を経由しても、必ず通過する基本ブロックを、制御フロ
ー情報８（図９参照）を参照して決定する。

【００６５】本実施例では、生存区間情報９（図１０参
照）の生存区間テーブルのエントリ＃１、＃２、＃３に
各々に対応する解放要求は、それぞれ１つであるため、
これらの生存区間の区間終了情報は、対応する解放情報
テーブルの解放情報の位置フィールド、ブロックフィー
ルドと同じとなる。

【００６６】図１０を参照して、エントリ＃４に対応す
る解放要求は、位置２８（基本ブロック＃４）、位置３
４（基本ブロック＃５）の２つ存在するが、位置２８が
属する基本ブロック＃４（開始位置２７、終了位置３
０）は、当該基本ブロックを通過した後に他の基本ブロ
ックへ制御が移行しないため、位置２８、３４のいずれ
を経由しても、必ず通過する基本ブロックは存在しない
ため、エントリ＃４を対象外とするために、生存区間テ
ーブルから、エントリ＃４を削除する。また、エントリ
＃４に対応する解放情報テーブル４も削除する。

【００６７】エントリ＃５に対応する解放要求は、位置
４１、４８の２つ存在し、いずれを経由しても必ず通過
する基本ブロックは基本ブロック＃９であるので、その
生存区間の終了位置情報のブロックフィールドには＃
９、位置フィールドには基本ブロックの先頭位置５０が
設定される。

【００６８】生存区間重複検査手段３は、生存区間情報
９（図１０参照）の生存区間テーブルの各エントリを参
照して、各エントリに対応する動的な記憶域の生存区間
の重複状況を調査して生存区間重複状況情報１０（図１
１参照）を生成する。図７に示したソースプログラムに
おいては、エントリ＃１に対応する動的な記憶域の生存
区間とエントリ＃２、＃３に対応する動的な記憶域の生
存区間が重複することとなる。

【００６９】グループ化手段４は、生存区間重複状況情
報１０（図１１参照）を参照して、生存区間が重複しな
い動的な記憶域群をグループ化し、グループ情報１１
（図１２参照）を生成する。

【００７０】生存区間情報９（図１０参照）の生存区間
テーブルのエントリ＃１とエントリ＃５、エントリ＃２
とエントリ＃３の２つのグループにグループ化するか、
エントリ＃２、エントリ＃３、エントリ＃５を１つのグ
ループにグループ化することが可能であるが、本実施例
では、それぞれの動的な記憶域のサイズの相違を考慮し
て、前者の２つのグループにグループ化する。

【００７１】その結果、図１２に示すように、グループ
情報１１には、グループ＃１（開始位置：１１、終了位
置：５０、サイズ：１２８）とグループ＃２（開始位
置：１５、終了位置：２２、サイズ：３００）の２つの
情報が生成される。

【００７２】プログラム変更手段５は、グループ化情報
１１（図１２参照）を参照し、図７に示したソースプロ
グラム６中の動的な記憶域の確保・解放要求をグループ
の開始位置、終了位置のみで行うように変更し、図１３
に示すようなソースプログラムを生成する。

【００７３】グループ＃１には生存区間情報９（図１０
参照）の生存区間テーブルのエントリ＃１とエントリ＃
５に対応する動的な記憶域が属するので、エントリ＃１
に対応する動的な記憶域に対する「ＡＬＬＯＣＡＴＥ
文」が出現する元ソースプログラム６の位置１１は、変
更後のソースプログラムにおいては、図１３に示すよう
に、位置１１−１、１１−２、１１−３のように変更さ
れる。追加された１１−１の「ＤＣＬ＃Ｐ１＃ＰＴ
Ｒ」でポインタを定義し、１１−２で「ＡＬＬＯＣＡＴ
ＥＡＳＥＴ（＃Ｐ１＃）」とポインタをもとの位置
１１から変更し、追加された１１−３で「Ｐ１＝＃Ｐ１
＃」と確保された記憶域のポインタ値をＰ１に代入して
いる。

【００７４】当該動的な記憶域に対する「ＦＲＥＥ文」
が出現するソースプログラム６（図７参照）の位置３６
は、変更後のソースプログラムにおいては、図１３に示
すように、削除されている。

【００７５】また、エントリ＃５に対応する動的な記憶
域に対する「ＡＬＬＯＣＡＴＥ文」が出現する元ソース
プログラム６の位置３７は、変更後のソースプログラム
においては、図１３に示す位置３７のように変更されて
いる。

【００７６】そして、当該動的な記憶域に対する「ＦＲ
ＥＥ文」が出現する元ソースプログラム６の位置４１、
４８は、変更後のソースプログラムでは削除され、グル
ープ＃１の終了位置である元ソースプログラム６の位置
５０は、変更後のソースプログラムにおいては、図１３
の位置５０−１、５０のように変更される。

【００７７】グループ＃２についてもグループ＃１と同
様にして、生存区間情報９（図１０参照）の生存区間テ
ーブルのエントリ＃２、エントリ＃３に対応する動的な
記憶域に対する「ＡＬＬＯＣＡＴＥ文」、「ＦＲＥＥ
文」が出現する元ソースプログラム６の該当位置が、変
更後のソースプログラムにおいては、図１３に示すよう
に変更される。

【００７８】以上により、本発明の実施例による動的記
憶域の割り付け方式の処理が完了し、ソースプログラム
６中の動的な記憶域に対する５つの「ＡＬＬＯＣＡＴＥ
文」、７つの「ＦＲＥＥ文」が、変更後のソースプログ
ラムにおいては、図１３に示すように、「ＡＬＬＯＣＡ
ＴＥ文」が３つ、「ＦＲＥＥ文」が４つに削減されてい
る。

【００７９】なお、上記実施例ではＰＬ／Ｉ言語による
動的記憶域の確保・解放のプログラム例を説明したが、
本発明のＰＬ／Ｉ言語に限定されるものでなく、他のプ
ログラミング言語による動的記憶域の確保・解放要求に
対しても適用可能である。

【００８０】

【発明の効果】以上説明したように、本発明によれば、
プログラム中の動的な記憶域の確保・解放に関する処理
のオーバヘッドの減少するという効果を奏する。

【００８１】この理由は、本発明においては、プログラ
ム中の動的な記憶域の確保・解放の要求を静的に解析可
能な範囲で解析して、生存区間が重複しない複数の動的
な記憶域を検出し、複数の動的な記憶域の共有化を図る
ことによって、動的な記憶域の確保・解放のための記憶
域管理用ライブラリ関数の呼出しを削減したことによ
り、少なくとも削減された記憶域管理用ライブラリ関数
分だけオーバヘッドが低減されるためである。

【図面の簡単な説明】

【図１】本発明の実施の形態を示す構成を示す図であ
る。

【図２】本発明の実施の形態におけるデータフロー情報
７の構成を示す図である。

【図３】本発明の実施の形態における制御フロー情報８
の構成を示す図である。

【図４】本発明の実施の形態における生存区間情報９の
構成を示す図である。

【図５】本発明の実施の形態における生存区間重複状況
情報１０の構成を示す図である。

【図６】本発明の実施の形態におけるグループ情報１１
の構成を示す図である。

【図７】本発明の実施例におけるソースプログラム６の
具体例を示す図である。

【図８】本発明の実施例におけるデータフロー情報７の
具体例を示す図である。

【図９】本発明の実施例における制御フロー情報８の具
体例を示す図である。

【図１０】本発明の実施例における生存区間情報９の具
体例を示す図である。

【図１１】本発明の実施例における生存区間重複状況情
報１０の具体例を示す図である。

【図１２】本発明の実施例におけるグループ情報１１の
具体例を示す図である。

【図１３】本発明の実施例におけるソースプログラム６
の変更後の具体例を示す図である。

【符号の説明】

１言語処理系２生存区間検出手段３生存区間重複検出手段４グループ化手段５プログラム変更手段６ソースプログラム７データフロー情報８制御フロー情報９生存区間情報１０生存区間重複状況情報１１グループ情報

Claims

【特許請求の範囲】

【請求項１】ソース・プログラムを解析し該プログラム
中で発行される動的な記憶域の確保・解放要求に関する
データフロー情報、及び該プログラムの制御フロー情報
に基づき、複数の動的な記憶域間での生存区間の重複状
況を検出し、共有可能な複数の記憶域を検出して共有さ
せることにより、動的な記憶域の確保・解放のための記
憶域管理用のライブラリ呼出しを削減するように前記ソ
ース・プログラムを自動修正する手段を備えたことを特
徴とする、動的記憶域割り付け方式。
【請求項２】プログラムの実行中に動的に記憶域を確保
・解放する機能を有するプログラミング言語に対する言
語処理系において、確保する記憶域のサイズがプログラムの翻訳時に判明す
る、動的な記憶域の確保要求を検出し、前記確保要求に
対して返却された記憶域を識別するポインタ値に関する
データフローと、プログラムの制御フローと、を解析し
て、前記ポインタ値が識別する記憶域に対する確保要求
から最も離れた位置の解放要求を検出し、これにより確
保された記憶域の生存区間を検出する生存区間検出手段
と、前記生存区間検出手段によって検出された複数の動的記
憶域の生存区間の重複を検査する生存区間重複検査手段
と、前記生存区間重複検査手段によって判明した生存区間の
重複状況を考慮して、同一の記憶域を共有可能な１又は
複数の動的記憶域にグループ化するグループ化手段と、一つのグループ中の動的記憶域のうち、最も大きいサイ
ズの記憶域を該グループ中で、その生存区間が最も早く
開始される動的記憶域の生存区間の先頭で確保し、該グ
ループ中でその生存区間が最も遅く終了する動的記憶域
の生存区間の最後で解放し、同一グループに属する動的
記憶域の確保・解放の要求を無効として、グループの先
頭で確保された記憶域を共有して利用するように、プロ
グラムを変更するプログラム変更手段と、を備えたことを特徴とする動的記憶域割り付け方式。