JPS60258648A - プログラム最適化処理方式 - Google Patents

プログラム最適化処理方式

Info

Publication number
JPS60258648A
JPS60258648A JP11434984A JP11434984A JPS60258648A JP S60258648 A JPS60258648 A JP S60258648A JP 11434984 A JP11434984 A JP 11434984A JP 11434984 A JP11434984 A JP 11434984A JP S60258648 A JPS60258648 A JP S60258648A
Authority
JP
Japan
Prior art keywords
optimization
processing
unit
flow
program
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP11434984A
Other languages
English (en)
Inventor
Tomoyuki Tani
谷 友幸
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP11434984A priority Critical patent/JPS60258648A/ja
Publication of JPS60258648A publication Critical patent/JPS60258648A/ja
Pending legal-status Critical Current

Links

Landscapes

  • Devices For Executing Special Programs (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データ処理システムにおけるプログラムの最
適化処理方式に関し、特にプログラム上での共通式処理
のための最適化範囲を限定することにより高速化を図っ
たプログラム最適化処理方式に関する。
〔従来の技術〕
原始プログラムのコンパイル処理では、生成した目的コ
ードを効率的なものにするため最適化処理が行われる。
最適化には定数式計算の先取り、ループ内不変式のルー
プ外移動、論理式の最適化、共通式の削除などがある。
この中で共通式の削除とは、プログラム内に同一構造の
式で変数の値が変わ6らないものが複数あった場合に、
最先の式だけを残して後の式を削除し、削除した場所で
は、最先の式の演算結果だけを参照してこれをそのまま
利用することにより、無駄な演算の繰り返しをなくすも
のである。次に共通式の探索処理を具体例で説明する。
第2図はプログラムの1例を示したもので、図中、■乃
至■はフローユニット(以後車にユニットということが
ある)である。共通式をめるためにはまず、各ユニット
内およびユニット間で同一構造の式が存在するか否かを
調べる。同一構造の式とは変数名および演算子が全て一
致している式のことである。図ではユニットの内の式“
’D+E”がユニット■内の式“’ D + E”と一
致し、またユニット■内の式“B十〇”がユニット■内
の式” B + C”と一致している。
次にこれら各相互に一致した式のうら、先行する弐の演
算結果を後続の式が利用可能であるが否かを制御フロー
にしたがって解析する。まずユニット■の式” B +
 C″については、゛ユニット■が条件分岐命令BCで
あることから、4)シもユニット■側のパス(Ll)が
選択されると、弐″B(C”は演算されないことが起こ
る。し、たがって、ユニット■における式” B + 
C”は、っ−二、ト■の式“B + C”の演算結果を
確実に利用できる保証がないので、これらを共通式とす
ることができない。すなわち、ユニット■からめて必ず
jfflaする最も近いユニ・7ト (バソクドミネー
タBDと呼ばれる)の■か■しか対象にすることができ
ない。
他方、1ニツト■の弐“’D+E”の演算はユニット■
での条件分岐命令の実行で、ユニット■、■のいずれが
選択されるかに拘ることなく実行される。そしてユニッ
ト■がらユニット■までの間に、変数り、Eの値が変更
されないがら、ユニット■で演算された式” D −1
−E″の結果は、ユニノl■において利用可能であり、
これらは共通式であると判定される。したがって、ユニ
ット■内の式“D + E ”は削除され、ユニット■
の式“D十E”の演算結果を参照するように書き替えら
れる。
〔発明が解決しようとする問題点〕
従来の共通式探索処理では、プログラムの制御フロー全
体を対象にして探索し、フロー解析の結果取捨している
が、たとえば中間にCALL文があるときには他のモジ
ュールに亘って解析することができないなど、プログラ
ム全体のフロー解析が無駄となるような場合があり、処
理効率が悪いという問題があった。
〔問題点を解決するための手段〕
変数の値は、2つの式の間にCA L 1文や文ラベル
、ループなどがあるとき変更されている可能性がある。
これを実際に確認するのは不0■能かもしくは煩雑な処
理が必要となる。このため本発明では、この問題を簡易
な手段で解決するため、このようなCALL文や文う−
・ル、ループが現れたところで無条件にフローを切断し
て最適化区間を分割設定し、必要最小限の範囲でのフロ
ー解析を行うようにするものであり、その構成は、プt
lダラムのコンパイル処理システl、において、プIコ
グラムのフローユニノ[ごとに文のう゛・\ル、CA 
LL文、ループ、END、1F等のその前後で共通式処
理の可否判定が困難となる要素を検出する手段と、該検
出された要素のフローフ、ニッ1−の直後に最適化処理
範囲の切断点を挿入して、最適化区間のフローユニット
のリンクを表示するテーブルを作成する処理手段とをそ
なえ、上記テーブルによりリンクを指示されたフローユ
ニットの範囲で共通式処理を実行することを特徴とする
ものである。
〔実施例〕
以下に本発明の詳細を実施例にしたがって説明する。
本発明により、最適化区間の設定は、次のような規則(
a)乃至(c)にしたがって実行される。
(a)制御フロー中に文うヘル、ループ入口、CA i
、 L、文等の変数の値の変化の有無を簡単には解析で
きない要素を検出したとき、その直後を最適化区間の切
断点とする。
(b)共通式処理はフローユニット内でけでなく、可能
な限りの他のフローユニットに亘って実行する。
(c)IF文のTHEN節内で最適化区間が切れてもI
F文の判定までとELSE節との間では共通式処理を可
能とする。ただし、IF文が終了するEND T Fの
後で別の最適化区間とする。第3図はこれを図示したも
のであり、■乃至■はフローユニットを示す。IF文の
判定ユニット■とTHEN節のCALLAまでのユニッ
ト■とが1つの最適化区間内に入り、判定ユニット■と
E T、、 S E節ユニット■とが1つの最適化区間
内に入る。そしてT HE N節のCΔ1. l。
A以後のユニット■と、END I F以後とは、それ
ぞれ別の最適化区間となる。
第1図は本発明方式の1実施例の説明図である。
図中、1は原始プログラム、2はコンパ・fう、3は目
的コード変換部、4は目的:l−ド、5は最適化処理部
、6は共通式処理部、7は最適化区間設定部、8は制御
フロー解析部、9(よ)C1−コ、二・ノドテーブル、
10は最適化区間テーブル、11は目的モジュールを表
している。
コンパイラ2は、原始プログラム1の処理を指示される
と、文、記号等の識別や(14文解析などの図示省略さ
れている処理を行った後、目的−1−1変換部3で中間
的な目的コード4を生成する。最適化処理部5は、目的
コー1′4について、前述したような各種の最適化処理
を実行する。共通式処理部6はその一部であり、最適化
区間設定部7および制御フロー解析部8を含んでいる。
最適化区間設定部7は、目的コート4のフローユニット
テーブル9にしたがって、前述した(a)、(b)、(
C)の規則を目的コードに適用し、最適化処理範囲を分
割し、最適化区間を設定する。
設定された結果は最適化区間テーブル10に登録される
。
゛ 制御フロー解析部8は、最適化区間テーブル10の
内容にしたがって各最適化区間を認識し、それぞれの範
囲内で共通式の探索を行い処理する。
このような最適化処理を経て、最終的にコンパイル処理
された結果は、目的モジュール11として出力される。
第4図は、最適化区間設定部7の処理例を示したもので
、(a)は第3図に示したプログラムに対応するフロー
ユニットテーブルの内容であり、(b)に示されるプロ
グラムのフロー、すなわち第3図のフローユニット■乃
至■のリンク関係を、ザクセノザリストを示したもので
ある。ここでフロ−ユニット1,3間のリンクは、(i
、j)で表されている。最適化区間設定部7は、それぞ
れのリンクにしたがって、順次のフローユニ・7トのテ
キスI−を解析し、CA L L文のイT無、1ト文の
整理などを行い、(b)のリンク中に鎖線で示される切
断点を検出する。切断点を検出されたフローユニットで
は、サクセノザリストの(i、j)を(i、0)に変更
し、さらに(0、j)を追加することにより、切断点を
表示させ、最適化区間テーブル10を作成する。第4図
の(C)は、このようにして作成された(b)のプロゲ
ラJ“、に対応する最適化区間テーブルの内容を表して
いる。
サクセソサリストが(0、j)である場合、新し。
い最適化区間がフローユニソ+−jから開始するものと
認識される。すなわち図示の例では、フローユニット■
および■の直前でそれぞれ最適化区間が開始される。
次に、制御フロー解析部8の動作について説明する。ま
ず、共通式処理の対象とするテキストを、演算タイプ別
、たとえば→、−等にしたがって、設定された最適化区
間内で別々に後方向に千−一−ンを張り、次に目的コー
ドのテキストを順次探索して行って、新しい式が出て来
たときにその式の演算タイプに対応するチェーンを選択
して、その中に同一式があるか否かを調べ、共通式処理
を行うものである。
第5図は、簡単化のため、第2図に示した演算タイプが
単一の加算式のみを含むプログラムの例について、各最
適化区間ごとに張られたテキストチェーンを示したもの
である。■乃至■はフローユニット番号であり、Pij
は、フローユニット番号0のフローユニットにおけるチ
ェーンのj番目のテキストアドレスを表している。
制御フロー解析部8では、処理時に、第6図に示す演算
タイプアドレスリストと、第7図に示す退避リストとを
作成し、保持する。
演算タイプアドレスリストには、演算タイプ(+、−1
×、・・・)ごとに、最も新しいテキストのアドレスが
記録されている。この最新テキストア1”レスはチェー
ンの先頭位置を示すポインタと、なる。
処理の際、プログラムの順次のテキストを、演算タイプ
アドレスリストに登録されている演算りイブと比較し、
ない場合にはその演算タイプと、テキストアドレスとを
登録し、ある場合にはその演算タイプのテキストチェー
ンを第5図に示すようにたどって共通式を探す。そして
共通式を見出せた場合には、その最新テキストを削除し
、先行テキストを参照させる処理を行う。他方共通式を
見出せなかった場合には、そのテキストをチェーンにつ
なぎそのアドレスで演算タイプアトレスリストの最新テ
キストアドレスを更新する。
テキストチェーンをたどる場合には、第7図の退避リス
トが使用される。退避リストは、各フローユニットの終
端で、演算タイプごとのテキストチェーンのリストをフ
ローユニット番号とともに退避格納したものである。処
理は後からさかのぼる方向で進められ、フローユニット
の先頭に達したとき、第1図の最適化区間テーブルを用
いてそのフローユニットのバックドミネータとなる先行
フローユニットをめ、退避リストより対応するテキスト
チェーンリストを取り出して処理を再開する。バノクド
ミネータが“0゛のとき、すなわら、テーブルのサクセ
ソサリストが(0、i)であれば、最適化区間の端に達
したことを意味するので、次のテキストの処理に移る。
このようにして全てのテキストについて共通式処理を実
行したとき、処理を終了する。
〔発明の効果〕
本発明によれば共通式処理の範囲を簡単に縮小すること
ができ、コンパイル処理時間の大幅な短縮を可能にする
。
【図面の簡単な説明】
第1図は本発明の1実施例の説明図、第2図はプログラ
ムの1例を示す説明図、第3図は本発明による最適化区
間設定例の説明図、第4図は最適化区間設定部の処理例
の説明図、第5図はテキストチェーンの説明図、第6図
は演算タイプアドレスリストの説明図、第7図は退避リ
ストの説明図である。 図中、1は原始プログラム、2はコンパイラ、4は目的
コード、6は共通式処理部、7は最適化区間設定部、8
は制御フロー解析部、9はフローユニソI〜テーブル、
10は最適化区間テーブルを表す。 特許出願人 富士通株式会社

Claims (1)

    【特許請求の範囲】
  1. プログラムのコンパイル処理システムにおいて、プログ
    ラムのフローユニットごとに文のラー・ル、CALL文
    、ループ、END I F等のその前後で共通式処理の
    可否判定が困難となる要素を検出する手段と、該検出さ
    れた要素のフローユニットの直後に最適化処理範囲の切
    断点を挿入して、最適化区間のフローユニットのリンク
    を表示するテーブルを作成する処理手段とをそなえ、上
    記テーブルによりリンクを指示されたフローユニットの
    範囲で共通式処理を実行することを特徴とするブ目グラ
    ム最適化処理方式。
JP11434984A 1984-06-04 1984-06-04 プログラム最適化処理方式 Pending JPS60258648A (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP11434984A JPS60258648A (ja) 1984-06-04 1984-06-04 プログラム最適化処理方式

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP11434984A JPS60258648A (ja) 1984-06-04 1984-06-04 プログラム最適化処理方式

Publications (1)

Publication Number Publication Date
JPS60258648A true JPS60258648A (ja) 1985-12-20

Family

ID=14635524

Family Applications (1)

Application Number Title Priority Date Filing Date
JP11434984A Pending JPS60258648A (ja) 1984-06-04 1984-06-04 プログラム最適化処理方式

Country Status (1)

Country Link
JP (1) JPS60258648A (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0756745A (ja) * 1993-08-13 1995-03-03 Nec Corp 言語処理プログラムのコンパイラ処理方式

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0756745A (ja) * 1993-08-13 1995-03-03 Nec Corp 言語処理プログラムのコンパイラ処理方式

Similar Documents

Publication Publication Date Title
Wahler et al. Clone detection in source code by frequent itemset techniques
US4860203A (en) Apparatus and method for extracting documentation text from a source code program
EP0643851B1 (en) Debugger program which includes correlation of computer program source code with optimized objet code
US6966055B2 (en) Optimizing post-link code
US20080288915A1 (en) Determining destinations of a dynamic branch
US5999739A (en) Method and apparatus for elimination of redundant branch instructions from a program
JPH0883185A (ja) コンパイラ
Gévay et al. Efficient control flow in dataflow systems: When ease-of-use meets high performance
US20020052856A1 (en) Method of data-dependence analysis and display for procedure call
Cetintemel et al. Making prompts first-class citizens for adaptive LLM pipelines
CN116089302A (zh) 一种针对Rust编程语言中UNSAFE代码片段缺陷的检测方法
Cserép et al. Integration of Incremental Build Systems Into Software Comprehension Tools.
JPH0756745A (ja) 言語処理プログラムのコンパイラ処理方式
Nan et al. Enabling near real-time nlu-driven natural language programming through dynamic grammar graph-based translation
US6694512B1 (en) Data processing device, data processing method and supply medium thereof
JPH0887417A (ja) コンパイラ装置
JPH09101880A (ja) プログラム分析装置
JPH0417031A (ja) 定数値伝播最適化方式
MARINOV An efficient syntax-preserving slide-based algorithm for program slicing
JPH0522272B2 (ja)
Neel et al. Removal of invariant statements from nested-loops in a single effective compiler pass
JP3167386B2 (ja) プログラム自動並列化方法
JP2723020B2 (ja) トレースデータ生成システム
JPH05120323A (ja) If文下ベクトル演算最適化方式
CN121209874A (zh) 编译决策的追溯方法、系统和电子设备