[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP4178278B2 - コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体 - Google Patents

コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体 Download PDF

Info

Publication number
JP4178278B2
JP4178278B2 JP2004154794A JP2004154794A JP4178278B2 JP 4178278 B2 JP4178278 B2 JP 4178278B2 JP 2004154794 A JP2004154794 A JP 2004154794A JP 2004154794 A JP2004154794 A JP 2004154794A JP 4178278 B2 JP4178278 B2 JP 4178278B2
Authority
JP
Japan
Prior art keywords
instruction
partial program
target
replacement
instruction sequence
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.)
Expired - Fee Related
Application number
JP2004154794A
Other languages
English (en)
Other versions
JP2005339021A (ja
Inventor
基弘 川人
秀昭 小松
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.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
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 International Business Machines Corp filed Critical International Business Machines Corp
Priority to JP2004154794A priority Critical patent/JP4178278B2/ja
Priority to US11/133,897 priority patent/US7707568B2/en
Publication of JP2005339021A publication Critical patent/JP2005339021A/ja
Priority to US12/167,421 priority patent/US20090007086A1/en
Application granted granted Critical
Publication of JP4178278B2 publication Critical patent/JP4178278B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/443—Optimisation
    • G06F8/4434—Reducing the memory space required by the program code

Landscapes

  • Engineering & Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)

Description

本発明は、コンパイラ、最適化方法、コンパイラプログラム、及び記録媒体に関する。特に、本発明は、最適化可能なことが予め分かっている命令の配列パターンを、その配列パターンに対応する置換先命令列に置換するコンパイラ、最適化方法、コンパイラプログラム、及び記録媒体に関する。
従来、最適化対象のプログラムの中から、予め定められたパターンに一致する命令列を検出し、その命令列を、そのパターンに対応して定められた他の命令列に置換する技術が提案されている。この技術によると、例えば、ある処理を実現する一連の命令群を、その処理と同一の処理結果を得る単一の命令に置換することにより、プログラムを最適化できる。置換先の命令の一例として、ＩＢＭコーポレーションのＳ／３９０アーキテクチャにおけるＴＲＴ命令が挙げられる。
ＴＲＴ命令は、所定の記憶領域を先頭から順次走査して、所定の条件を満たす値が格納されているアドレス等を出力する命令である（非特許文献４参照。）。図１６は、ＴＲＴ命令による処理に対応する制御フローグラフである。ＴＲＴ命令による処理は、記憶領域bytearrayの先頭から順に記憶領域に格納された値を変数chに順次読み出し、その値が条件cond1からcondNの何れかを満たす場合に終了する一連の処理に対応する。コンパイラは、このような一連の処理を、単一のＴＲＴ命令に置換することにより、プログラムを最適化できる。
実施例において言及する文献は以下の通りである（非特許文献１〜３参照）。
Jianghai Fu. Directed graph pattern matching and topological e mbedding.Journal of Algorithms, 22(2):372-391, February 1997. S.S. Muchnick. Advanced compiler design and implementation, Morgan Kaufmann Publishers, Inc., 1997. Arvind Gupta and Naomi Nishimura. Finding Largest Subtrees and Smallest Supertrees, Algorithmica, Vol. 21, No. 2, pp. 183-210, 1998 http://publibz.boulder.ibm.com/epubs/pdf/dz9zr002.pdf のページ7-180
しかしながら、最適化対象のプログラムが、予め定められたパターンと完全に一致することは稀である。このような場合、従来は最適化を諦めていた。この結果、ＴＲＴ命令等のアーキテクチャが独自に有している命令を有効に利用できない場合があった。
そこで本発明は、上記の課題を解決することのできるコンパイラ、最適化方法、コンパイラプログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
上記課題を解決するために、本発明の第１の形態においては、最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した対象部分プログラムの少なくとも一部を、置換対象パターンに対応して定められた置換先命令列に置換して最適化するコンパイラ装置であって、コンピュータにより、対象プログラムが有する複数の部分プログラムのうち、置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出部と、変形前後において対象部分プログラムの処理結果が変更されないことを条件として、コンピュータにより対象部分プログラムを変形して、対象部分プログラムを、命令の実行順序が置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形部と、コンピュータにより、命令列変形部により変形された対象部分プログラムにおける、命令の実行順序が置換対象パターンにおける命令の実行順序と同一となる命令列を、置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部とを備えるコンパイラ装置、当該コンパイラ装置を用いる最適化方法、当該コンパイラ装置としてコンピュータを機能させるコンパイラプログラム、及び当該コンパイラプログラムを記録した記録媒体を提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
本発明によれば、アーキテクチャが独自に有している命令を有効に利用することができる。
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、コンパイラ１０の機能ブロック図である。コンパイラ１０は、予め定められた複数の命令を有する置換対象パターンを検出し、検出したその置換対象パターンを、置換対象パターンに対応して定められた置換先命令列に置換する。置換先命令列は、置換対象パターンと比較して効率的に実行される命令列であり、一例として、アーキテクチャ独自の高速な命令を含む。即ちこれにより、最適化対象の対象プログラムを、より効率的に実行される命令列に最適化することを目的とする。
コンパイラ１０は、最適化候補検出部１００と、対象部分プログラム検出部１１０と、命令列変形部１２０と、命令列置換部１３０とを備える。最適化候補検出部１００は、最適化の対象となる部分プログラムの候補を検出する。例えば、最適化候補検出部１００は、対象プログラムのうち、置換対象パターンに含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを検出する。ここで、部分プログラムとは、例えば、メソッド、関数、又は手続きと呼ばれるプログラムの処理単位であってもよいし、ループ処理等のように制御フローの性質に基づいて定まる命令列であってもよい。
そして、対象部分プログラム検出部１１０は、最適化候補検出部１００により検出された複数の部分プログラムのうち、置換対象パターン２０に類似する部分プログラムを対象部分プログラム４０として検出する。例えば、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラム４０として検出する。より具体的には、対象部分プログラム検出部１１０は、ある２つの命令について、処理内容が互いに同一であり、その命令から出力する制御フローの数が互いに同一であり、かつ、制御フローの移行先の命令が互いに同一である場合に、それらの命令が互いに対応すると判断する。
命令列変形部１２０は、対象部分プログラム４０のうち、置換対象パターン２０に含まれる命令に対応する命令以外の命令、及び、置換対象パターン２０と異なる実行の依存関係を有する命令に対して、対象部分プログラム４０に含まれる命令間の依存関係を置換対象パターン２０に一致させる変形を行う。命令列変形部１２０は、必要に応じて、その他の命令に対して変形を行ってもよい。変形された対象部分プログラムを対象部分プログラム５０とする。
命令列置換部１３０は、命令列変形部１２０により変形された対象部分プログラム５０を、置換対象パターン２０に対応して定められた置換先命令列に置換する。例えば、コンパイラ１０は、置換先命令列の構造を示す置換先命令テンプレート３０における各変数を、その変数に対応する対象部分プログラム５０における変数に置き換えることにより、置換先命令列を生成する。その結果、コンパイラ１０は、置換先命令列を含めた対象プログラムを結果部分プログラム６０として出力する。
図２（ａ）は、置換対象パターン２０の具体例を示す。置換対象パターン２０は、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄを有する。そして、置換対象パターン２０は、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄにおける、命令間の実行の依存関係を定める。命令間の実行の依存関係とは、例えば命令間の制御フローである。この制御フローによると、命令Ａの実行後に命令Ｂが実行され、命令Ｂの実行後に命令Ｃが実行され、命令Ｃの後に命令Ｄが実行される。そして、命令Ｄの実行後に命令Ａが再度実行される。
これに代えて、置換対象パターン２０は、命令間の制御依存関係を定めてもよいし、データ依存関係を定めてもよい。また、置換対象パターン２０は、制御依存関係及びデータ依存関係の双方を定めた依存グラフであるPDG(Program Dependence Graph)であってもよい。即ち、置換対象パターン２０は、置換対象パターン２０に含まれる複数の命令の各々をノードとし、これら複数の命令間の実行の依存関係を有向エッジとした依存グラフであればよい。
図２（ｂ）は、対象部分プログラム４０の第１の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、命令Ｄ、及び命令Ａを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。このため、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、置換対象パターン２０が、命令間で循環する依存関係を定める場合において、対象部分プログラム検出部１１０は、置換対象パターン２０が定める依存関係と同一でありかつ循環の位相が異なる命令列を対象部分プログラム４０として検出できる。
そしてこの場合、命令列変形部１２０が対象部分プログラム４０を変形することなく、命令列置換部１３０は、対象部分プログラム４０を置換先命令列に置換する。この例に加えて、対象部分プログラム検出部１１０は、置換対象パターン２０が定める依存関係と同一でありかつ循環の位相も同一の命令列（即ち完全に一致する命令列）を、対象部分プログラム４０として検出してもよい。この場合も同様に、命令列変形部１２０が対象部分プログラム４０を変形することなく、命令列置換部１３０は、対象部分プログラム４０を置換先命令列に置換する。
図２（ｃ）は、対象部分プログラム４０の第２の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。このため、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、対象部分プログラム検出部１１０は、置換対象パターン２０における実行の依存関係と異なる順序で実行される命令列を含む部分プログラムを、対象部分プログラム４０として検出できる。
そしてこの場合、命令列変形部１２０は、対象部分プログラム４０における命令の実行順序を変更しても対象部分プログラム４０の処理結果が変更されないことを条件として、対象部分プログラム４０における命令の実行順序をその依存関係に基づいて変更する。具体的には、命令列変形部１２０は、命令Ｂが命令Ｃの処理結果に依存しない場合には、命令Ｂ及び命令Ｃの実行順序を入れ換える。この結果対象部分プログラム５０が生成される。そして、命令列置換部１３０は、命令の実行順序が変更された対象部分プログラム５０を、置換先命令列に置換する。
図２（ｄ）は、対象部分プログラム４０の第３の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、命令Ｄ、及び命令Ｅを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。従って、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる何れの命令にも対応しない命令である余剰命令Ｅをループ処理内に含む部分プログラムを、対象部分プログラム４０として検出できる。
そしてこの場合、命令列変形部１２０は、対象部分プログラム４０のループ処理内に含まれる余剰命令の実行結果が、ループ処理の繰り返しによらず同一であることを条件として、その余剰命令をそのループ処理の外で実行させる変形を行う。これに代えて、命令列変形部１２０は、対象部分プログラム４０のループ処理を、余剰命令及び余剰命令以外の命令列を各々実行する２つのループ処理に分割してもよい。ループ処理の分割についての詳細は、非特許文献２において公知であるので、説明を省略する。そして、命令列置換部１３０は、余剰命令を除外したループ処理を、置換先命令列に置換する。
図２は、対象部分プログラム４０の第４の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、及び命令Ｄを含む。従って、この部分プログラムにおいて、置換対象パターン２０に含まれる何れかの命令（即ち命令Ｃ）が不足する。この場合、まず、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる全ての命令のうち、この部分プログラムにおいてそれらの命令に対応する命令の割合を算出する。そして、対象部分プログラム検出部１１０は、算出したその割合が、予め定められた基準割合以上であることを条件として、その部分プログラムを対象部分プログラム４０として検出する。続いて、この場合における処理を、図３を用いて説明する。
図３は、図２（ｅ）に対応する対象部分プログラム４０及び対象部分プログラム５０の具体例を示す。命令列変形部１２０は、置換対象パターン２０に含まれる全ての命令に対応する命令のうち、対象部分プログラム４０において不足している不足命令である命令Ｃを、対象部分プログラム４０に追加する。そして、命令列変形部１２０は、その不足命令の追加により変化する対象部分プログラム４０の処理結果をその不足命令が未追加の場合における処理結果に戻すキャンセル命令を生成する。そのキャンセル命令を命令Ｃ-1とする。なお、命令列変形部１２０は、その効果を打ち消すべく、命令Ｃの前後でそれぞれ実行される２つの命令の組を生成してもよい。これらの命令を命令Ｃ-1 before及び命令Ｃ-1 afterとする。
一例として、命令列変形部１２０は、命令Ｃの処理結果が格納される記憶領域の値を命令Ｃに先立って退避する退避命令を命令Ｃ-1 beforeとして生成する。また、命令列変形部１２０は、その記憶領域の値を命令Ｃの実行後に復帰する復帰命令を命令Ｃ-1 afterとして生成する。生成された対象部分プログラム５０を図３（ａ）に図示する。そして、命令列変形部１２０は、退避命令及び復帰命令を対象部分プログラム５０外で実行させる変形を行う。変形された対象部分プログラム５０を図３（ｂ）に図示する。そしてこの場合、命令列置換部１３０は、命令Ｃを含む対象部分プログラム５０を、置換先命令列に置換する。
なお、好ましくは、対象部分プログラム検出部１１０は、各々の部分プログラムについて、不足命令及び退避命令等をその部分プログラムに追加した場合に増加する処理時間の見積もりを算出する。そして、対象部分プログラム検出部１１０は、命令列置換部１３０によりその部分プログラムが置換先命令列に置換された場合に短縮される処理時間の見積もりを算出する。そして、対象部分プログラム検出部１１０は、増加するその処理時間が、短縮されるその処理時間より小さい場合に、その部分プログラムを対象部分プログラムとして検出する。これにより、効率化できる部分のみを最適化することができる。
更に他の例として、置換対象パターン２０に含まれるある比較命令と、対象部分プログラム４０に含まれる比較命令とで、比較対象の変数のみが異なる場合には、命令列変形部１２０は、対象部分プログラム４０に含まれる比較命令における、その変数との比較対象の定数を変更してもよい。例えば、置換対象パターン２０が、命令switch(ch)を含み、対象部分プログラム４０が、命令switch(ch+1)を含む場合、命令列変形部１２０は、対象部分プログラム４０におけるcase文の定数から１を減じる変形を行う。そして、命令列変形部１２０は、対象部分プログラム４０における命令switch(ch+1)を命令switch(ch)に変形する。この結果、命令列置換部１３０は、対象部分プログラム４０に含まれる命令を置換対象パターン２０に一致させることができる。
図４は、コンパイラ１０が対象プログラムを最適化する処理を示すフローチャートである。最適化候補検出部１００は、最適化の候補となる部分プログラムを検出する（Ｓ４００）。具体例を述べる。まず、最適化候補検出部１００は、置換対象パターン２０に含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する。
例えば、最適化候補検出部１００は、置換対象パターン２０がロード命令を含む場合には部分プログラムがロード命令を含むことを条件として、その部分プログラムを最適化の候補と判断する。同様に、最適化候補検出部１００は、置換対象パターン２０がストア命令を含む場合には部分プログラムがストア命令を含むことを条件として、その部分プログラムを最適化の候補と判断する。また、アクセス対象のデータの型とは、データ表現の範囲を示す型であるbyte, int, float, 及びdoubleの他に、データの種類を示す型（配列変数、インスタンス変数、及びクラス変数）を含む。
また、最適化候補検出部１００は、置換対象パターン２０がループ処理を含む場合においては、ループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する。ループ処理とは、例えば、プログラムを制御フローグラフとして表した場合における強連結成分に対応する命令列をいう。また、最適化候補検出部１００は、置換対象パターン２０に含まれるループ処理と比較してループ誘導変数の増分が同一であるループ処理を含むことを更に条件として、最適化の候補となる部分プログラムを検出する。
また、最適化候補検出部１００は、そのループ処理が、予め定められた基準回数以上繰り返し処理されることを更に条件として、最適化の候補となる部分プログラムを検出してもよい。以上の処理により、最適化を試みる範囲を絞り込むことができるので、コンパイルに要する処理時間を短縮できる。この結果、本実施例に示す技術を、実行時コンパイラ等の動的コンパイラに適用しやすくできる。
なお、好ましくは、最適化候補検出部１００は、利用者が所望する最適化の程度を示す最適化レベルが設定されている場合には、その最適化レベルに応じて、最適化の候補を検出する基準を変更する。例えば、最適化候補検出部１００は、より高い最適化レベルが設定されている場合には、より低い最適化レベルが設定されている場合と比較して、より多くの部分プログラムを最適化の候補として検出する。更に、利用者の設定等によっては、最適化候補検出部１００は、Ｓ４００における処理を行わなくてもよい。
続いて、対象部分プログラム検出部１１０は、最適化候補の部分プログラムのうち、置換対象パターン２０に含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する（Ｓ４１０）。置換対象パターン２０がループ処理を含む場合について、この処理の具体例を説明する。対象部分プログラム検出部１１０は、ループ処理内の命令については、命令の対応のみを判断し、依存関係の一致を判断しない。一方、対象部分プログラム検出部１１０は、ループ処理外の命令については、命令の対応のみならず、依存関係の一致をも判断する。
即ち、対象部分プログラム検出部１１０は、各々の部分プログラムについて、その部分プログラムが、そのループ処理に含まれる全ての命令に対応する命令をループ処理内に含み、かつその部分プログラムにおけるループ処理外の全ての命令が、置換対象パターン２０が定める依存関係に従う場合に、その部分プログラムを対象部分プログラムとして検出する。これにより、依存関係が同一で循環の位相が異なるループ等を適切に検出できる。
更に詳細には、まず、対象部分プログラム検出部１１０は、各々の部分プログラムについて、その部分プログラムに含まれる複数の命令の各々をノードとし、それらの複数の命令の実行の依存関係を有向エッジとした依存グラフを生成する。そして、対象部分プログラム検出部１１０は、グラフの同型性を判定するアルゴリズムにより、生成した依存グラフと、置換対象パターン２０を示す依存グラフとの同型性を判断する。
一例として、対象部分プログラム検出部１１０は、非特許文献１に記載のtopological embeddingの技術により、置換対象パターン２０と同型の依存グラフを検出してもよい。これに代えて、対象部分プログラム検出部１１０は、非特許文献２に記載の方法に基づき、置換対象パターン２０との共通部分が最大のプログラム片を検出することにより、置換対象パターン２０と同型の依存グラフを検出してもよい。これらの技術によると、置換対象パターン２０の依存グラフにおけるノードとノードとの間に、任意のノードが含まれている場合であっても、同型性があると判断できる。そのため、図２(ｄ)の命令列を対象部分プログラムとして検出できる。
また、ループ処理の依存グラフは、無限に続く木構造として取り扱う。そこで、(ｂ)については、A-＞B-＞C-＞D-＞A-＞B-＞C-＞……と判断し、同型性を見つけることができる。(c)については、ループを展開するとA-＞C-＞B-＞D-＞A-＞C-＞B-＞D-＞A……となる。このアルゴリズムは先ほど述べたようにノード間に任意のノードが含まれることを許している。そのため、先ほどの下線を引いた部分がA-＞B-＞C-＞Dと接続されているため、これもパターンと同型性があると判断される。
このように、対象部分プログラム検出部１１０は、各々の当該部分プログラムにおいて、置換対象パターン２０に含まれる全ての命令に対応する命令が、置換対象パターン２０における各命令の実行の依存関係の示す実行順序で実行されると判断した場合に、部分プログラムを対象部分プログラムとして検出できる。これにより、例えば、図２(b)(c)(d)の各々の命令列を、対象部分プログラムとして検出できる。
更に、以下に説明する方法でtopological embeddingの技術を拡張することにより、対象部分プログラム検出部１１０は、図２（ｄ）の命令列を、対象部分プログラムとして検出できる。具体的には、まず、topological embeddingのアルゴリズムにおいて、置換対象パターン２０の何れかのノードに対応するノードが部分プログラムに不足すると判断する部分を、実際のノードの不足に関わらず、当該ノードが検出されたと判断されるように変更する。
そして、対象部分プログラム検出部１１０は、不足するノードが検出される毎にそのノードの識別情報を記録することにより、不足するノードの集合を求める。この結果、対象部分プログラム検出部１１０は、不足するノードの集合に基づいて、置換対象パターン２０に含まれる全ての命令のうち、部分プログラムにおいてそれらの命令に対応する命令の割合を算出できる。更に、対象部分プログラム検出部１１０は、このアルゴリズムにより、図２の（ｂ）から（ｅ）に示した特徴の２つ以上を有する命令列を検出することもできる。
続いて、命令列変形部１２０は、対象部分プログラムのうち、置換対象パターン２０に含まれる命令に対応する命令以外の命令、及び、置換対象パターン２０と異なる実行の依存関係を有する命令に対して、対象部分プログラム４０に含まれる命令間の依存関係を置換対象パターン２０に一致させる変形を行う（Ｓ４２０）。命令列置換部１３０は、変形された対象部分プログラム５０を、置換対象パターンに対応して定められた置換先命令列に置換する（Ｓ４３０）。なお、対象部分プログラム検出部１１０により検出された全ての命令列が、置換先命令列に置換できるとは限らない。即ち、命令列変形部１２０が、対象部分プログラム４０を変形できず、命令列置換部１３０が命令列を置換できない場合もある。
続いて、コンパイラ１０が対象プログラムを入力して最適化する４つの例を順次説明する。
（第１例）
図５（ａ）は、第１の例における置換対象パターン２０を示す。置換対象パターン２０は、図１６に示した命令列を検出するための置換対象パターンである。図１６に示した命令列において、switch命令（２）の分岐先は、２から２５６までの数で可変である。従って、このswitch命令を適切に検出するには、２から２５６までのそれぞれの数の分岐先を有する２５５個の置換対象パターン２０を生成する必要があるとも考えられる。しかし、多くの置換対象パターン２０と部分プログラムとを比較するのには、多くの処理時間を要するので効率的でない。
そこで、対象部分プログラム検出部１１０は、図示する置換対象パターン２０を用いて対象部分プログラムを検出する。この置換対象パターン２０は、複数の条件の何れかが満たされた場合に置換対象パターン２０の外部の命令に制御を移す複数分岐命令（例えばswitch命令（２））について、その複数分岐命令から外部の命令に制御を移す複数の制御フローを代表する１つのエッジである代表エッジを有する。
そして、対象部分プログラム検出部１１０は、部分プログラムの制御フローを示す依存グラフが、その代表エッジに対応するエッジを有する場合に、その部分プログラムがその複数分岐命令を含むと判断する。即ち、対象部分プログラム検出部１１０は、置換対象パターン２０の複数分岐命令が有するエッジより、部分プログラムの複数分岐命令が有するエッジが多いことを条件として、これらの複数分岐命令が互いに対応すると判断する。
図５（ｂ）は、第１の例における置換先命令テンプレート３０を示す。なお、本図は、置換先命令テンプレート３０に含まれる命令による処理内容を示すプログラムソースコードを示している。実際には、置換先命令テンプレート３０は、所定の中間コード又は機械語により記述されていてもよい。
置換先命令テンプレート３０において、変数bytearrayは、TRT命令が比較の対象とする値を格納する記憶領域のアドレスを示す。また、変数iは、その記憶領域を走査するためのインデックスを示す。また、命令列置換部１３０は、変数bytearrayが有する値と同数の値を格納する記憶領域を確保し、その記憶領域のアドレスを変数tableに格納する。例えば、bytearrayの記憶領域におけるインデックスiの値が、ループを終了する条件を満たす場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。
図６は、コンパイラ１０が最適化する対象部分プログラム４０の第１の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムを示す。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０によると、変数dataにより定められる記憶領域を順次走査し、定数GREATERTHAN又は定数０を検出した場合に、ループ処理を終了する。また、定数０が検出された場合にはメソッドコールからリターンする。
本図と図５（ａ）とを比較して明らかなように、置換対象パターン２０及び対象部分プログラム４０では、記憶領域から値を読み出す命令の処理順序が異なる。具体的には、置換対象パターン２０においては命令（１）により記憶領域から値が読み出される一方、対象部分プログラム４０においては命令（ａ）及び命令（ｅ）により記憶領域から値が読み出される。従来の技術によると、変数名等の違いを考慮せずにプログラムの同型性を判断することはできるものの、命令の配置が異なる場合にプログラムの同型性を判断できない。即ち、本図の対象部分プログラム４０を、最適化対象として検出できなかった。
これに対して、本実施例におけるコンパイラ１０によると、図５（ａ）の命令（１）が図６（ｂ）の命令（ａ）及び命令（ｅ）に対応することが検出できる。また、図５（ａ）の命令（２）が図６（ｂ）の命令（ｂ）及び命令（ｃ）に対応することが検出できる。更に、図５（ａ）の命令（３）が図６（ｂ）の命令（ｄ）に対応することが検出できる。
そして、命令列変形部１２０は、命令（ｂ）及び命令（ｃ）が連続して実行され、かつ、図５（ａ）の命令（２）に変形可能である旨を検出する。更に、命令列変形部１２０は、置換対象パターン２０及び対象部分プログラム４０において変数chの依存関係が同一である旨を検出する。更に、命令列変形部１２０は、置換対象パターン２０及び対象部分プログラム４０において、記憶領域のインデックス変数についての依存関係が同一である旨を検出する。更に、命令列変形部１２０は、対象部分プログラム４０が置換対象パターン２０と比較して余剰命令を含まない旨を検出する。以上の全ての条件が充足された場合に、命令列置換部１３０は、対象部分プログラム４０を、置換対象パターン２０に基づいて置換先命令列に置換する。
図７は、第１の例における結果部分プログラム６０を示す。命令列置換部１３０は、置換先命令列を生成する場合に、変数tableが示す記憶領域を生成する。例えば、変数dataの記憶領域におけるインデックスiの値が、GREATERTHAN又は0である場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。そして、命令列置換部１３０は、tableの記憶領域におけるその他の値を０に初期化する。
なお、この処理から明らかなように、ループ処理を終了するか否かが、インデックスiの値に基づいて定まるのであれば、命令列置換部１３０は、命令列を最適化できる。従って、対象部分プログラム検出部１１０は、ある部分プログラムと置換対象パターン２０とで、switch命令の参照対象が互いに異なる場合であっても、ループ処理を終了するか否かがインデックスiの値に基づいて定まることを条件として、その部分プログラムを対象部分プログラム４０として検出してもよい。一例として、ある部分プログラムが命令switch(map1[ch])を含む場合、対象部分プログラム検出部１１０は、配列変数map1が定数配列であることを条件として、その部分プログラムを対象部分プログラム４０として検出してもよい。
結果部分プログラム６０による処理を説明する。結果部分プログラム６０により、コンピュータは、while命令（３）及びTRT命令（５）により、変数dataにより定まる記憶領域を２５６バイトずつ走査する。ここで、TRT命令（５）は、ループ処理を２５６回繰り返す処理と比較して極めて高速に実行できるので、変数dataにより定まる記憶領域の走査を高速化できる。一例として、その記憶領域の最初の２５６バイト以内に０又はGREATERTHANが格納されていた場合には、命令（１）から命令（９）がこの順に実行される。このためループ処理を実行しないので、極めて効率が高い。
以上、第1例によると、命令列置換部１３０は、while命令及びswitch命令等の２以上の命令で実現される処理を、その処理と同一の処理を行う１つの命令であるＴＲＴ命令に置換することができる。
なお、第1例の変形例として、置換対象パターン２０が、変数bytearrayの値がnullであるか否かを判定するnullcheck命令を含む場合が考えられる。例えば、nullcheck命令は、命令（１）が無効なアドレスから値を読み出すことを防止する目的で、命令（１）が実行される毎に、命令（１）が実行される直前で実行される場合が多い。
ここで、bytearrayの値は、ループの繰り返しによらず一定である。このため、nullcheck命令の実行結果は、ループの繰り返しによらず同一である。従って、このような場合には、命令列変形部１２０がnullcheck命令をループ処理の外で実行させるので、命令列置換部１３０は、nullcheck命令を除外したループ処理を、置換先命令列に置換できる。
（第２例）
図８は、コンパイラ１０が最適化する対象部分プログラム４０の第２の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムである。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０により、コンピュータは、変数bytesにより定められる記憶領域を、変数offsetが示すインデックスにより順次走査する。そして、負の値が検出された場合に、ループ処理を終了する。
対象部分プログラム４０において、ループ処理は、変数offset及び変数countの２つの誘導変数を有する。即ち、本図の対象部分プログラム４０と、図５（ａ）の置換対象パターン２０とでは、プログラムの構造が明らかに異なる。従って、従来のコンパイラは、対象部分プログラム４０を最適化の対象と判断することはできなかった。
本実施例におけるコンパイラ１０によると、対象部分プログラム検出部１１０は、部分プログラムが置換対象パターン２０と比較して余剰命令を有している場合であっても、その部分プログラムを対象部分プログラム４０として検出できる。具体的には、図５（ｂ）の命令（１）が図８（ｂ）の命令（ａ）に対応することが検出できる。また、図５（ｂ）の命令（２）が図８（ｂ）の命令（ｂ）に対応することが検出できる。更に、図５（ｂ）の命令（３）が図６（ｂ）の命令（ｃ）に対応することが検出できる。
そしてこの場合、命令列変形部１２０は、余剰命令を実行させる新たなループ処理を生成する。この結果、命令列置換部１３０は、対象部分プログラムにおける余剰命令以外の命令を置換先命令列に置換できる。なお、コンパイラ１０は、新たに生成されたループ処理を更に最適化してもよい。即ち例えば、コンパイラ１０は、新たに生成されたループ処理を、変数countの値を変数offsetの値から算出する処理に最適化できる。
図９は、第２の例における結果部分プログラム６０を示す。命令列置換部１３０は、置換先命令列を生成する場合に、変数tableが示す記憶領域を生成する。例えば、変数bytesの記憶領域におけるインデックスiの値が、負の値である場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。そして、命令列置換部１３０は、tableの記憶領域におけるその他の値を０に初期化する。
結果部分プログラム６０による処理を説明する。結果部分プログラム６０により、コンピュータは、while命令（３）及びTRT命令（５）により、変数bytesにより定まる記憶領域を２５６バイトずつ走査する。ここで、TRT命令（５）は、ループ処理を２５６回繰り返す処理と比較して極めて高速に実行できるので、変数bytesにより定まる記憶領域の走査を高速化できる。一例として、その記憶領域の最初の２５６バイト以内に負の値が格納されていた場合には、命令（１）から命令（９）がこの順に実行される。このためループ処理を実行しないので、極めて効率が高い。
（第３例）
図１０は、コンパイラ１０が最適化する対象部分プログラム４０の第３の例を示す。本図は、対象部分プログラム４０の処理内容を示すソースプログラムである。対象部分プログラム４０により、コンピュータは、変数bytesにより定められる記憶領域を、変数offsetが示すインデックスにより順次走査する。そして、負の値が検出された場合に、ループ処理を終了する。更に、このループ処理において、変数aにより定まる記憶領域を先頭から順に０で初期化する。
対象部分プログラム４０において、ループ処理は、変数offset及び変数countの２つの誘導変数を有する。即ち、本図の対象部分プログラム４０と、図５（ａ）の置換対象パターン２０とでは、プログラムの構造が明らかに異なる。そしてこの場合、従来のコンパイラは、対象部分プログラム４０を最適化の対象と判断することはできなかった。
本実施例におけるコンパイラ１０によると、対象部分プログラム検出部１１０は、部分プログラムが置換対象パターン２０と比較して余剰命令を有している場合であっても、その部分プログラムを対象部分プログラム４０として検出できる。従って、命令列変形部１２０は、対象部分プログラム４０におけるループ処理を、余剰命令及び余剰命令以外の命令列を各々実行する２つのループ処理に分割する。
図１１は、第３の例における結果部分プログラム６０を示す。（ａ）は、命令列置換部１３０により置換された置換先命令列を含む結果部分プログラム６０である。図９と同様に、while命令及び条件分岐命令が、TRT命令に置換される。そして、変数aにより定まる記憶領域を初期化する余剰命令は、新たに生成されたループ処理（２）及び（３）により実行される。
（ｂ）は、コンパイラ１０により更に最適化された結果部分プログラム６０を示す。本図に示すように、コンパイラ１０は、変数aにより定まる記憶領域を初期化するループ処理を、ＸＣ命令に最適化してもよい。ＸＣ命令によれば、所定のサイズの記憶領域を所定の値で初期化できる。ループ処理により２５６バイトの記憶領域を順次初期化する処理と比較して、ＸＣ命令は極めて高速に実行される。このため、対象プログラムを更に効果的に最適化することができる。
なお、ＸＣ命令は、定数オペランドにより指定されたサイズの記憶領域を初期化することができる。例えば、命令（１）は、定数である２５６バイトのサイズの記憶領域を初期化するＸＣ命令である。更に、ＩＢＭコーポレーションのＳ／３９０によるＥＸＥＣＵＴＥ命令によれば、プログラムの実行中に、定数オペランドにより指定された値を変更することができる（非特許文献４のページ７−１０８参照。）。これにより、実質的に、ＸＣ命令は、レジスタにより指定されたサイズの記憶領域を初期化できる。例えば、本図の命令（３）は、初期化する記憶領域のサイズを示す定数オペランドが、ＥＸＥＣＵＴＥ命令により変数Ｔ＿ｉｎｃｃｏｕｎｔの値に変更されたＸＣ命令を示す。
（第４例）
図１２は、コンパイラ１０が最適化する対象部分プログラム４０の第４の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムである。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０によれば、コンピュータは、変数inputに格納されたデータにおける値が１のビットの数をカウントし、変数outputに格納する。このプログラムによると、変数inputのビット数に比例して処理時間が増加するので、効率的でない。
図１３は、第４の例における結果部分プログラム６０を示す。命令列置換部１３０は、図１２の対象部分プログラム４０を、本図の結果部分プログラム６０に変更する。結果部分プログラム６０によると、コンピュータは、変数inputにおける値が１のビットの数を、対象部分プログラム４０と比較して高速に実行できる。このように、命令列置換部１３０は、特定の命令に置換する処理のみならず、アルゴリズムを置換する処理を行ってもよい。即ち、命令列置換部１３０は、より長い処理時間を要するアルゴリズムによる処理の命令列を、より短い処理時間を要する他のアルゴリズムによる処理の命令列に置換してもよい。
図１４は、本実施例の効果を説明する図である。図６に示した対象部分プログラム４０と、図７に示した結果部分プログラム６０との速度の比較を行った。本図の表は、ループ処理を終了するまでに走査するデータの数に対する、対象部分プログラム４０に対する結果部分プログラム６０の速度の向上比率である。本図においては、２５６個のデータに対する向上比率まで示しているが、２５６を超える数のデータに対しては、更に向上比率が高まることも確かめられた。
また、本図に示すように、平均で８以上のデータを走査する場合においては、最適化によりプログラムの実行を効率化できることが分かる。即ち例えば、コンパイラ１０は、８以上のデータを走査する可能性が高いループ処理のみを選択して最適化することにより、プログラム全体の実行効率を高めることができる。
図１５は、コンパイラ１０として機能するコンピュータ５００のハードウェア構成の一例を示す。コンピュータ５００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＢＩＯＳ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、コンピュータ５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、コンピュータ５００の起動時にＣＰＵ１０００が実行するブートプログラムや、コンピュータ５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
コンピュータ５００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出されコンピュータ５００にインストールされて実行される。このプログラム、例えばコンパイラプログラムがコンピュータ５００に働きかけて行わせる動作は、図１から図１４において説明したコンピュータ５００における動作と同一であるから、説明を省略する。
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ５００に提供してもよい。
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
図1は、コンパイラ１０の機能ブロック図である。 図２は、置換対象パターン２０及び対象部分プログラム４０の具体例を示す。 図３は、図２（ｅ）に対応する対象部分プログラム４０及び対象部分プログラム５０の具体例を示す。 図４は、コンパイラ１０が対象プログラムを最適化する処理を示すフローチャートである。 図５は、置換対象パターン２０及び置換先命令テンプレート３０の第１の例を示す。 図６は、コンパイラ１０が最適化する対象部分プログラム４０の第１の例を示す。 図７は、第１の例における結果部分プログラム６０を示す。 図８は、コンパイラ１０が最適化する対象部分プログラム４０の第２の例を示す。 図９は、第２の例における結果部分プログラム６０を示す。 図１０は、コンパイラ１０が最適化する対象部分プログラム４０の第３の例を示す。 図１１は、第３の例における結果部分プログラム６０を示す。 図１２は、コンパイラ１０が最適化する対象部分プログラム４０の第４の例を示す。 図１３は、第４の例における結果部分プログラム６０を示す。 図１４は、本実施例の効果を説明する図である。 図１５は、コンパイラ１０として機能するコンピュータ５００のハードウェア構成の一例を示す。 図１６は、ＴＲＴ命令による処理に対応する制御フローグラフである。
符号の説明
１０ コンパイラ
２０ 置換対象パターン
３０ 置換先命令テンプレート
４０ 対象部分プログラム
５０ 対象部分プログラム
６０ 結果部分プログラム
１００ 最適化候補検出部
１１０ 対象部分プログラム検出部
１２０ 命令列変形部
１３０ 命令列置換部

Claims (16)

  1. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換して最適化するコンパイラ装置であって、
    前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出部と、
    変形前後において前記対象部分プログラムの処理結果が変更されないことを条件として、前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形部と、
    前記命令列変形部により変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
    を備えるコンパイラ装置。
  2. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換する最適化するコンパイラ装置であって、
    前記置換対象パターンに含まれる全ての命令に対応する命令のうち何割の命令がそれぞれの前記部分プログラムに含まれているかを示す割合が、所定の基準割合以上である前記部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出部と、
    前記置換対象パターンに含まれる命令のうち、前記対象部分プログラムに不足している不足命令を前記対象部分プログラムに追加し、且つ、前記対象プログラムにおける処理結果を、前記不足命令を追加する前の処理結果に戻すためのキャンセル命令を前記対象部分プログラムに追加し、前記不足命令および前記キャンセル命令を追加した前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形部と、
    前記命令列変形部により変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
    を備えるコンパイラ装置。
  3. 前記対象プログラムのうち、前記置換対象パターンに含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
    前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
    請求項１又は２に記載のコンパイラ装置。
  4. 前記対象プログラムのうち、前記置換対象パターンに含まれるループ処理と比較してループ誘導変数の増分が同一であるループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
    前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
    請求項１又は２に記載のコンパイラ装置。
  5. 前記対象プログラムのうち、予め定められた基準回数以上繰り返し処理されるループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
    前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
    請求項１又は２に記載のコンパイラ装置。
  6. 前記対象部分プログラム検出部は、前記置換対象パターンに含まれる何れの命令にも対応しない命令である余剰命令をループ処理内に含む部分プログラムを、前記対象部分プログラムとして検出し、
    前記命令列変形部は、前記対象部分プログラムのループ処理内に含まれる前記余剰命令の実行結果が、ループ処理の繰り返しによらず同一であることを条件として、当該余剰命令を当該ループ処理の外で実行させ、
    前記命令列置換部は、前記余剰命令を除外した前記ループ処理を、前記置換先命令列に置換する
    請求項１記載のコンパイラ装置。
  7. 前記対象部分プログラム検出部は、前記置換対象パターンに含まれる何れの命令にも対応しない命令である余剰命令をループ処理内に含む部分プログラムを、前記対象部分プログラムとして検出し、
    前記命令列変形部は、前記対象部分プログラムのループ処理を、前記余剰命令及び前記余剰命令以外の命令列を各々実行する２つのループ処理に分割し、
    前記命令列置換部は、前記余剰命令以外の命令列を、前記置換先命令列に置換する
    請求項１記載のコンパイラ装置。
  8. 前記命令列変形部は、前記不足命令の処理結果が格納される記憶領域の値を前記不足命令に先立って退避する退避命令と、当該記憶領域に退避した前記値を前記不足命令の実行後に復帰する復帰命令とを、前記キャンセル命令として生成し、前記対象部分プログラム外で実行させる
    請求項２記載のコンパイラ装置。
  9. 前記対象部分プログラム検出部は、各々の当該部分プログラムについて、前記置換対象パターンと比較して当該部分プログラムにおいて不足している命令を当該部分プログラムに追加した場合に増加する処理時間が、前記命令列変形部により前記部分プログラムが前記置換先命令列に置換された場合に短縮される処理時間より小さい場合に、当該部分プログラムを前記対象部分プログラムとして検出する
    請求項２記載のコンパイラ装置。
  10. 前記命令列置換部は、前記対象部分プログラムが有する２以上の命令を、当該２以上の命令による処理と同一の処理を行う１つの命令に置換する
    請求項１又は２記載のコンパイラ装置。
  11. 前記命令列置換部は、より長い処理時間を要するアルゴリズムによる処理の命令列を、より短い処理時間を要する他のアルゴリズムによる処理の命令列に置換する
    請求項１又は２記載のコンパイラ装置。
  12. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換して最適化する最適化方法であって、
    対象部分プログラム検出部が、前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出段階と、
    変形前後において前記対象部分プログラムの処理結果が変更されないことを条件として、命令列変形部が、前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形段階と、
    命令列置換部が、前記命令列変形段階において変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換段階と
    を備える最適化方法。
  13. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換する最適化する最適化方法であって、
    対象部分プログラム検出部が、前記置換対象パターンに含まれる全ての命令に対応する命令のうち何割の命令がそれぞれの前記部分プログラムに含まれているかを示す割合が、所定の基準割合以上である前記部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出段階と、
    命令列変形部が、前記置換対象パターンに含まれる命令のうち、前記対象部分プログラムに不足している不足命令を前記対象部分プログラムに追加し、且つ、前記対象プログラムにおける処理結果を、前記不足命令を追加する前の処理結果に戻すためのキャンセル命令を前記対象部分プログラムに追加し、前記不足命令および前記キャンセル命令を追加した前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形段階と、
    命令列置換部が、前記命令列変形段階において変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換段階と
    を備える最適化方法。
  14. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換して最適化するコンパイラ装置として、コンピュータを機能させるコンパイラプログラムであって、
    前記コンピュータを、
    前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出部と、
    変形前後において前記対象部分プログラムの処理結果が変更されないことを条件として、前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形部と、
    前記命令列変形部により変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
    して機能させるコンパイラプログラム。
  15. 最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンに類似する対象部分プログラムを検出し、検出した前記対象部分プログラムの少なくとも一部を、前記置換対象パターンに対応して定められた置換先命令列に置換する最適化するコンパイラ装置として、コンピュータを機能させるコンパイラプログラムであって、
    前記コンピュータを、
    前記置換対象パターンに含まれる全ての命令に対応する命令のうち何割の命令がそれぞれの前記部分プログラムに含まれているかを示す割合が、所定の基準割合以上である前記部分プログラムを、前記置換対象パターンに類似する対象部分プログラムとして検出する対象部分プログラム検出部と、
    前記置換対象パターンに含まれる命令のうち、前記対象部分プログラムに不足している不足命令を前記対象部分プログラムに追加し、且つ、前記対象プログラムにおける処理結果を、前記不足命令を追加する前の処理結果に戻すためのキャンセル命令を前記対象部分プログラムに追加し、前記不足命令および前記キャンセル命令を追加した前記対象部分プログラムを変形して、前記対象部分プログラムを、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列と、他の命令列とに分割する命令列変形部と、
    前記命令列変形部により変形された前記対象部分プログラムにおける、命令の実行順序が前記置換対象パターンにおける命令の実行順序と同一となる命令列を、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
    して機能させるコンパイラプログラム。
  16. 請求項１４及び請求項１５の何れかに記載のコンパイラプログラムを記録した記録媒体。
JP2004154794A 2004-05-25 2004-05-25 コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体 Expired - Fee Related JP4178278B2 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2004154794A JP4178278B2 (ja) 2004-05-25 2004-05-25 コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体
US11/133,897 US7707568B2 (en) 2004-05-25 2005-05-20 Compiler optimization
US12/167,421 US20090007086A1 (en) 2004-05-25 2008-07-03 Compiler Optimization

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2004154794A JP4178278B2 (ja) 2004-05-25 2004-05-25 コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体

Publications (2)

Publication Number Publication Date
JP2005339021A JP2005339021A (ja) 2005-12-08
JP4178278B2 true JP4178278B2 (ja) 2008-11-12

Family

ID=35426897

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2004154794A Expired - Fee Related JP4178278B2 (ja) 2004-05-25 2004-05-25 コンパイラ装置、最適化方法、コンパイラプログラム、及び記録媒体

Country Status (2)

Country Link
US (2) US7707568B2 (ja)
JP (1) JP4178278B2 (ja)

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060200811A1 (en) * 2005-03-07 2006-09-07 Cheng Stephen M Method of generating optimised stack code
JP2008059279A (ja) * 2006-08-31 2008-03-13 Internatl Business Mach Corp <Ibm> 文字列出力処理を最適化する技術
JP2008097249A (ja) 2006-10-11 2008-04-24 Internatl Business Mach Corp <Ibm> プログラム中の命令列をより高速な命令に置換する技術
US8656381B2 (en) * 2006-12-07 2014-02-18 International Business Machines Corporation Presenting machine instructions in a machine-independent tree form suitable for post-link optimizations
US7430733B1 (en) * 2007-11-15 2008-09-30 International Business Machines Corporation Method for validation of binary code transformations
JP2009205264A (ja) * 2008-02-26 2009-09-10 Nippon Telegr & Teleph Corp <Ntt> ウェブサービス要求処理装置、ウェブサービス要求処理方法、及びウェブサービス要求処理システム
US9134977B2 (en) * 2010-02-26 2015-09-15 Red Hat, Inc. Compiler operation for handling conditional statements
FR2960988B1 (fr) * 2010-06-03 2013-03-15 Invia Methode de compression et de decompression d'un programme executable ou interpretable
GB2514618B (en) * 2013-05-31 2020-11-11 Advanced Risc Mach Ltd Data processing systems
GB2521367A (en) * 2013-12-17 2015-06-24 Ibm Adaptable and extensible runtime and system for heterogeneous computer systems
EP3177990B1 (en) * 2014-08-29 2021-03-17 Huawei Technologies Co., Ltd. Method for compiling a source code
JP6547477B2 (ja) * 2015-07-15 2019-07-24 富士通株式会社 ソースコード最適化装置、ソースコード最適化プログラム及びオブジェクトコード生成方法
US10776087B2 (en) * 2018-06-25 2020-09-15 Intel Corporation Sequence optimizations in a high-performance computing environment
US10970073B2 (en) * 2018-10-02 2021-04-06 International Business Machines Corporation Branch optimization during loading
US11379200B2 (en) * 2020-01-30 2022-07-05 Oracle International Corporation Method for applying graph-specific compiler optimizations to graph analysis programs
CN112947999B (zh) * 2021-03-10 2022-06-28 超睿科技(上海)有限公司 一种精简指令集计算机指令功能扩展的方法及装置

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0721032A (ja) 1993-07-01 1995-01-24 Mitsubishi Electric Corp プログラム最適化処理方式
JP3311462B2 (ja) * 1994-02-23 2002-08-05 富士通株式会社 コンパイル処理装置
US6343375B1 (en) * 1998-04-24 2002-01-29 International Business Machines Corporation Method for optimizing array bounds checks in programs
US6463582B1 (en) * 1998-10-21 2002-10-08 Fujitsu Limited Dynamic optimizing object code translator for architecture emulation and dynamic optimizing object code translation method
GB2345989A (en) * 1999-01-23 2000-07-26 Ibm Executing defined sequences of prolog instructions.
JP3470948B2 (ja) * 1999-01-28 2003-11-25 インターナショナル・ビジネス・マシーンズ・コーポレーション 動的コンパイル時期決定方法、バイトコード実行モード選択方法、及びコンピュータ
JP2000284970A (ja) 1999-03-29 2000-10-13 Matsushita Electric Ind Co Ltd プログラム変換装置及びプロセッサ
US6507947B1 (en) * 1999-08-20 2003-01-14 Hewlett-Packard Company Programmatic synthesis of processor element arrays
US6892380B2 (en) * 1999-12-30 2005-05-10 Texas Instruments Incorporated Method for software pipelining of irregular conditional control loops
US7386839B1 (en) * 2002-11-06 2008-06-10 Valery Golender System and method for troubleshooting software configuration problems using application tracing
US20050108695A1 (en) * 2003-11-14 2005-05-19 Long Li Apparatus and method for an automatic thread-partition compiler

Also Published As

Publication number Publication date
US7707568B2 (en) 2010-04-27
JP2005339021A (ja) 2005-12-08
US20090007086A1 (en) 2009-01-01
US20050268293A1 (en) 2005-12-01

Similar Documents

Publication Publication Date Title
US20090007086A1 (en) Compiler Optimization
US8104026B2 (en) Compiler register allocation and compilation
US8291398B2 (en) Compiler for optimizing program
US8266603B2 (en) Technique for allocating register to variable for compiling
US6983458B1 (en) System for optimizing data type definition in program language processing, method and computer readable recording medium therefor
JP5966509B2 (ja) プログラム、コード生成方法および情報処理装置
US8176100B2 (en) System for storing and managing objects
JP2000035893A (ja) デ―タ処理システムの配列の静的初期化方法、デ―タ処理方法、並びにデ―タ処理システム及びその制御手順をコンピュ―タに実行させるプログラムを記憶したコンピュ―タ読み取り可能な記憶媒体
JP2008059279A (ja) 文字列出力処理を最適化する技術
JP2004062520A (ja) 最適化装置、コンパイラプログラム、最適化方法、及び記録媒体
US8296750B2 (en) Optimization of a target program
JP2004362216A (ja) コンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体
US20150212804A1 (en) Loop distribution detection program and loop distribution detection method
JP4042972B2 (ja) 最適化コンパイラ、コンパイラプログラム、及び記録媒体
US7526761B2 (en) Exception handling compiler apparatus, program, recording medium, and compiling method
US7383544B2 (en) Compiler device, method, program and recording medium
JP2005173645A (ja) プログラム開発支援装置、プログラム開発支援方法、プログラム、及び、記録媒体
JP2018163505A (ja) 検索プログラム、情報処理装置および検索方法
US20090119632A1 (en) Method for supporting determination of design process order
US20040187101A1 (en) Compiler, compiler program, recording medium, and compiling method
JP4522216B2 (ja) 画像処理装置
US20230034198A1 (en) Using dynamic data structures for storing data objects
JP6545406B2 (ja) 高位合成装置、高位合成方法および高位合成プログラム
JP6547477B2 (ja) ソースコード最適化装置、ソースコード最適化プログラム及びオブジェクトコード生成方法
JP2002259987A (ja) 画像処理装置及び方法、記憶媒体、コンピュータ・プログラム

Legal Events

Date Code Title Description
A871 Explanation of circumstances concerning accelerated examination

Free format text: JAPANESE INTERMEDIATE CODE: A871

Effective date: 20071210

A975 Report on accelerated examination

Free format text: JAPANESE INTERMEDIATE CODE: A971005

Effective date: 20080108

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20080205

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20080218

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20080520

RD14 Notification of resignation of power of sub attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7434

Effective date: 20080530

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20080603

A911 Transfer to examiner for re-examination before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20080709

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20080729

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20080806

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110905

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120905

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130905

Year of fee payment: 5

LAPS Cancellation because of no payment of annual fees