JPH10161882A - 述語型コード処理システム - Google Patents

Abstract

(57)【要約】 【課題】述語型コードにおける述語間の干渉の可能性を
判断するため述語を大域的に分析するシステムおよび方
法を提供する。 【解決手段】制御フローと明示的述語を単一のパーティ
ション・グラフにマップして両者を統一的に取り扱うこ
とによって述語の間の関係が大域的に追跡される。これ
によってプロシジャ全体にわたる述語関係の分析が可能
となる。そのため、本発明のシステムは、各述語に関す
る領域を決定する手段、決定した領域の各々を互いに素
の部分集合に細分化する手段、および、述語の大域的関
係を捕捉するため細分化された領域の各々に基づいてパ
ーティション・グラフを構築する手段を備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、高性能マイクロプ
ロセッサにおける述語コードの使用に関するもので、干
渉の可能性を判断するため述語を大域的に分析するシス
テムおよび方法に関するものである。

【０００２】

【従来の技術】現代の高性能マイクロプロセッサにおけ
る広範囲の機械資源を完全に利用するためには、個々の
基本ブロックを越えた並列性を開拓することが必要であ
る。異なる基本ブロックからの命令をブール述語によっ
てガードされた直線的コードに変換することを可能にす
ることによって、述語化された実行に関するアーキテク
チャ上のサポートが命令レベルの並列性を増加させる。
しかしながら、述語化された実行は、また，最適化コン
パイラに対して大きな挑戦を提示する。

【０００３】以下の記述において、V. Kathail、M. Sch
lansker、B. Rau３氏著の"HPL Playdoh Architecture S
pecification: Version 1.0, Hewlett-Packard Laborat
ories Technical Report, HPL-93-80, Feb. 1993"に記
載のHPL Playdohアーキテクチャで提供される一般的述
語化実行モデルのアーキテクチャ・サポートが前提とさ
れている。このアーキテクチャでは、命令の実行は限定
述語(qualifying predicate)によってガードされる。次
の形式の比較命令が述語を設定するために提供される。 p1,p2 = cmpp.<d1><d2> (a rel b) if qp 述語p1およびp2は、２つの宛先を持つ述語である。<d1>
および<d2>の各々は、比較命令に関するタイプおよびモ
ードを指定する２字記述子である。記述子の最初の文字
によって指定される、unconditionalすなわち無条件
(u)、conditionalすなわち条件付き(c)、parallel-orす
なわち並列ＯＲ(o)、およびparallel-andすなわち並列
ＡＮＤ(a)という４つの比較タイプがある。各タイプ
は、記述子の２番目の文字によって指定されるnormal m
odeすなわち通常モード(n)およびcomplement modeすな
わち補完モード(c)を持つ。記述子<d1>および<d2>は、
宛先述語p1およびp2をそれぞれ制御する。条件(a rel
b)は、relはeq(等しい)、ne(等しくない)、lt(未満)等
が実際に記入されて，２つの変数aおよびbの論理比較を
示す形式である。述語qpは、qualifying predicate(限
定述語)を表す。

【０００４】無条件および条件つきのタイプに関する議
論を単純化するため、以下の記述において、それらをそ
れぞれcmpp.un.ucおよびcmpp.cn.ccという形式に一般化
する。従って、無条件タイプの比較に関しては、p1およ
びp2の値は相補的である。比較タイプがand(or)でqpが
真であれば、(on)目標述語(例えばp1)は，p1の前の値と
AND(OR)された(a rel b)の結果に等しい。

【０００５】次の表１は、宛先述語がこれらの比較命令
でどのように設定されているかをまとめたものである。
この表において、TおよびFは、true(真)およびfalse
(偽)をそれぞれ意味し、Xは"該当せず"を表し、ncは結
果が変わらない(unchanged)ことを表す。また、特別述
語レジスタp0の存在が仮定される。このレジスタから読
みとられるすべては常に真であり、書き込まれるものす
べては無視される。

【０００６】

【表１】qp (a rel b) un uc cn cc on oc an ac F X F F nc nc nc nc nc nc T T T F T F T nc nc F T F F T F T nc T F nc

【０００７】下記表２に(1)として記載されているコー
ド部分は、グローバルな範囲における述語関係を認識す
る重要性を示している。xおよびyの両方は、異なる基本
ブロック内で定義され使用される。干渉について調べる
ため、pの下のxの使用がrの下のxの定義に向かってelse
節へ伝播される。このプロセスの間sの下のyの定義を交
差させている間、pおよびsが互いに素であることが確認
されない限り、xとyの間の干渉が推定される。コードを
調べることによって、pおよびsがthenおよびelse節にそ
れぞれ定義されているので、pおよびsの両方が同時に真
であることは決してあり得ないことがわかる。しかしな
がら、pおよびsの間の互いに素という関係を体系的に確
認する大域的分析が必要とされる。この関係は、複合ブ
ロックまたは基本ブロックに基づく分析によって補足す
ることはできない。大域述語分析を用いればpおよびrが
互いに素であることを確認することができる。従って、
rの下のxの定義は、pの下のxの使用に決して到達するこ
とができないので、この定義は、はたらいていない。

【０００８】

【表２】(1) p,q,r,s = false if (..) then { p,q = cmpp.un.uc if true x = .. if p } else { r,s = cmpp.un.uc (...) if true x = .. if r y = .. if s } .. = x if p .. = y if s

【０００９】従来技術のコンパイラは、述語階層グラフ
(すなわちpredicate hierarchy graph,ＰＨＧ)を使用し
て、複合ブロックにおける述語のすべてについてブール
式を追跡した。この方法は、S.A. Mahike、D.C. Lin、
W.Y Chen、R.E. HankおよびR. A. Bringnann著の"Effec
tive Compiler Support for Predicated Execution Usi
ng Hyperblock," In Proc. of the 25th Annual Int'l
Symp. on Microarchitecture, pp. 45-54, Dec. 1992に
記載されている。上記文献では、複合ブロックの範囲に
わたって分析が行われるが、それは大域的には拡張され
ない。ＰＨＧのようなコンパニオン・データ構造がコー
ドと共に維持されると、プログラムが変更するときは必
ずデータ構造も更新されなければならない。

【００１０】N.J. Waters, S.A. Mahike, W.-M.W. Hwu
およびB.R. Rau各氏共著の"ReverseIf-conversion," In
Proc, of the SIGPLAN'93 Conf. on Programming Lang
uageDesign and Implementation, pp. 290-299, June 1
993によって提唱された反転if変換方式がある。これ
は、データ・フロー領域からの述語を、よく知られてい
る制御フロー領域に対応づけるものである。この方式の
主な欠点は、再対応付けプロセスの間に元々存在しなか
った制御経路がいくつか作成される可能性がある点であ
る。この事象は、典型的には、コードがif変換され次に
スケジュールされ、従ってコード順序が入れ替わる時、
発生する。このコードが反転if変換される時、存在しな
い経路はが多くの分析および変換における保守的処置を
引き起こす可能性がある。

【００１１】Alexandre E. Eichenberger、Edward S.Da
vidson両氏著の"Register Allocation for Predicated
Code," In Proc. of the 28th Annual Int'l Symp. on
Microarchitecture, November 1995は、述語をＰ-事実
(論理的に不変の表現)として表すことによって、述語が
直面するレジスタ割当て問題を解決する。このメカニズ
ムは、Ｐ-事実の２つのセットの交差部を記号パッケー
ジを使用して偽に単純化することができるならば，２つ
の生きた範囲は干渉しないと結論づけている。このアプ
ローチもまた複合ブロックの範囲に制限されていて、述
語の数に関する潜在的な指数的コンパイル時間行動を所
与とすれば、実用性を制限している。

【００１２】

【発明が解決しようとする課題】従って、データ・フロ
ー分析のようなコンパイル分析の間，人工的または不要
なステップをプロセスに付加することなく、述語の意味
論を考慮することのできる述語型実行システムの必要性
が当業界に存在する。

【００１３】

【課題を解決するための手段】本発明は、述語型コード
が存在する場合種々のコンパイラ分析および変換フェー
ズの精度および効果を向上させるため述語の間の関係を
分析するシステムおよび方法を提供する。本発明の述語
分析システムは、プロシージャ全体の範囲に基づいて述
語の間の関係を取得するため大域的に動作する。更に、
本発明のシステムおよび方法は、制御フローと述語を単
一の統一されたフレームワークに結合し、後続の最適化
および分析フェーズがこのフレームワークに照会を行う
ことを可能にする。

【００１４】述語分析における従来技術は、一般的に、
ｉｆ変換単一入口複数出口制御フロー領域である複合ブ
ロックに基づいている。本発明においては、制御フロー
・グラフ(以下Control Flow Graphの頭文字をとってＣ
ＦＧと略称する場合がある)の各ノードは、直線的シー
ケンスの述語型コードを含む単一入口単一出口領域であ
る基本ブロックである。この表現形式の１つの利点は、
この形式がいまだにコンパイラ分析および最適化にとっ
て最もよく知られた表現であるということである。本発
明は、ＣＦＧが単一の開始ノードおよび単一の終了ノー
ドを持つと仮定する。本発明の大域述語分析は、プロシ
ージャ全体における制御フローおよびコード・ストリー
ムに基づく。大域述語分析は、述語が異なる基本ブロッ
クにおいて定義され使用される場合一層明確な述語関係
を作成する。

【００１５】本発明は、従来技術において定義された表
記法をプロシージャ全体にに拡大する。トレースは、Ｃ
ＦＧにおける開始ノードから終了ノードまでの非周期的
な経路について実行される命令のすべてを含む。pが真
の時トレースについての命令のすべてが実行されるとす
れば、このトレースは述語pの領域(すなわちドメインdo
main)に属する。異なる基本ブロックにおいて定義され
る述語を関連づける鍵は、これらの基本ブロックの間で
の到達可能性を分析することである。述語に関する場合
と同様に、本発明は、基本ブロックの領域を、その基本
ブロックが実行されるトレースのすべてであると定義す
る。従って、ある基本ブロックに別の基本ブロックから
到達することができるなら(またはその逆)、これらの２
つの基本ブロックは、"互いに素(すなわちdisjoint)"で
はない。この到達可能性情報が大域パーティション・グ
ラフに表され、述語の存在に関係なく、基本ブロックの
間の関係を追跡することができる。

【００１６】制御フローおよび述語を一様に取り扱うた
め、本発明は、各基本ブロックに１つの述語を割り当て
る。本発明は、区別の必要があれば、基本ブロックに割
り当てられる述語を制御述語(control predicate)と呼
び、命令ストリームに明示的に現れる述語を実体述語(m
aterialized predicate)と呼ぶ。基本ブロックの制御述
語は、基本ブロックが実行されるか否かを制御する条件
のすべてを組み合わせる述語と見なされる。本発明は、
制御述語および実体述語を含む１つの完全な述語パーテ
ィション・グラフの構築に基づいた大域述語分析を実行
する。この単一大域パーティション・グラフによって、
プログラム分岐を通る条件付き実行ならびに述語型実行
の意味論を追跡することが可能となる。注：制御述語が
また実体述語に実体化されれば、それらが同じ領域を共
有しパーティション・グラフの中の同じノードにマップ
されることを本発明のｉｆ変換は保証する。このことに
より、述語分析の精度が更に向上する。

【００１７】後述のグラフ構築メカニズムは、持続的デ
ータ構造の更新を必要とすることなく、最適化ルーチン
全体を通して呼び出されることができる。これは、ｉｆ
変換の前でも後でも実行できる。この柔軟性は、本発明
が制御フローおよび実体述語を統一的方法で取り扱うと
いう事実による。ｉｆ変換が実体述語作成の主要源では
あるが、高水準疑似コード拡張のようなフェーズも述語
型コードを生成することができる。実体述語の間の大域
的関係を知ることによって、ｉｆ変換の前後のデータ・
フロー分析が一層正確になる得る。

【００１８】本発明の１つの技術的利点は、述語の間の
関係を分析する大域的技術の開発であり、それらの関係
を後続のコンパイル分析または変換フェーズが照会する
ことができるということである。制御フローと述語の間
の関係を統合するため述語分析を使用することは本発明
の別の利点である。

【００１９】本発明のシステムおよび方法は、多くの既
知のコンピュータ上で動作することができる。例えば
は、ヒューレット・パッカード社から市販のＰＡ−ＲＩ
ＳＣ８２００である。

【００２０】発明の課題を解決する手段として、本発明
は、複数の述語を持つ述語型コードを処理するシステム
を提供する。該システムは、各述語に関する領域を決定
する手段、決定した領域の各々を互いに素の部分集合に
細分化する手段、および、述語の大域的関係を捕捉する
ため細分化された領域の各々に基づいてパーティション
・グラフを構築する手段を備える。

【００２１】

【発明の実施の形態】図１のＡおよびＢは、それぞれ、
オリジナルの制御フローおよびＩＦ変換コードの例を示
す。ＩＦ変換は、すべての６つの基本ブロックを述語型
コードを持つ１つの基本ブロックに変換する。S1および
S2を含む基本ブロックでの切り替えポイントの各々は、
無条件タイプの比較命令に変換される。S4を含む基本ブ
ロックでの合流ポントは、無条件タイプの１つの比較命
令とＯＲタイプの１つの比較命令の組合せに変換され
る。

【００２２】本明細書の記述において、述語の間の関係
を追跡するため述語パーティション・グラフの概念が使
用される。説明を簡略にするため、述語は、各述語がた
だ一度だけ静的に定義される静的単一割り当て形式を持
つと仮定する。このような形式をStatic Single Assign
mentの頭文字をとって以下ＳＳＡと呼称する。

【００２３】しかし、これは本発明の実施形態上の要件
ではない。図１のＢに示されるように、p4は２回定義さ
れている。ＳＳＡ形式でのp4への参照を記述するため、
関連定義および使用が以下の表３の(3)に示されるよう
な中間形式に変換される。

【００２４】

【表３】 (3) ... p4_1 = cmpp.uc (...) if true ... p4_2 = p4_1 | px, where px = cmpp,un (s2 cond) if p2 ... S4 if p4_2 ...

【００２５】述語の間の関係を記述するため実行集合の
概念を使用する。まず直線的コードで以下の表記法を定
義し、後に制御フローを取り入れるようにそれらを拡張
する。実行トレースは、直線的コードで最初から最後ま
で実行される命令のすべてを含む。pが真の時トレース
についての命令のすべてが実行されるならば、このトレ
ースは述語pの領域(または基本実行集合)に属してい
る。pの領域は、そのようなトレースのすべてを含む。
注：領域の概念は例示目的のためだけのもので、それら
の経路を列挙する必要はない。曖昧でなければ、pの領
域を意味するため単にpを使用することもできる。

【００２６】図２で示されるように、述語のパーティシ
ョンは、複数の"互いに素"の部分集合への述語領域の分
割であり、従って、それらの部分集合の和集合は領域に
等しい。例えば、命令p1,p2=cmpp.un,uc ( .. . )if p3
を図で表せば、図２のようになる。p3が真の時、p1およ
びp2の値は常に相補的である。言い換えると、p1および
p2の両方が真である場合非周期的実行経路は存在しな
い。p1またはp2が真であれば、p3が真でなければならな
いことを導出することができる。

【００２７】述語パーティション・グラフG=(V,E)にお
いて、Vの中の各ノードpは述語pを表し、各エッジ(p,q)
は、qがパーティションの部分集合であるようなパーテ
ィションがpに存在することを表す。Gにおけるエッジが
指示され、同じパーティションから作成されたエッジは
同じラベルを与えられる。異なるパーティションによっ
て２つの所与のノードの間に複数のエッジが存在するの
で、Ｇは指示された非周期的複数グラフである。全体集
合p0がユニークなルートであれば、パーティション・グ
ラフは完全である。これは、述語分析で使用されるアル
ゴリズムによって必要とされる場合、あらゆるノードを
ルートから到達可能とさせる。パーティション・グラフ
は述語関係に近似するので、同じコード・ストリームに
関して、いろいろな精度を持つ異なるパーティション・
グラフを作成することができる。

【００２８】図１のＢで示されたｉｆ変換されたコード
のためのパーティション・グラフが図３のＢに示され
る。図３のＢは領域がどのように分割されるかを理解す
るのに役立つ。パーティション・グラフのルートp0は、
l1でp2およびp3に細分化される。l4で、p2は、p5、およ
びこのパーティションを完成させるために作成される暗
黙的述語pxに細分化される。命令l1およびl2は両方とも
に無条件の比較タイプを持ち、同じ条件について調べる
ので、これらの２つの命令は、本質的に値合同である。
従って、p3およびp4_1は常に同じ値を持ち、同じ述語ノ
ードにマップされることができる。l5において、pxおよ
び4_1和集合がp4_2に関する領域を形成する。p4_2の補
集合は、p5であり、親述語としてp0を、子述語としてp4
_2およびp5を持つ別のパーティションを生成する。この
ステップは、p4_2をルートから到達可能にするため必要
である。上記は、図３のＡに示されている。

【００２９】パーティション・グラフが構築されると、
そのグラフに基づく大域的述語照会システムを構築し
て、述語型関係に関する(以下のような)多数の異なる照
会をサポートすることができる。

【００３０】isDisjoint(p.q.): 述語pの領域が述語qの
領域と重なるかどうかを照会する。２つの述語が同じパ
ーティションの異なるエッジを経由して２つの共通の先
祖に到達することができれば、それら２つの述語は"互
いに素"である。例えば、図３のＡにおいて、p3およびp
5は互いに素であるが、p2およびp4_2は互いに素ではな
い。注：この点は、pxがp2およびp4_2の部分集合である
ように示されている図３のＢの領域関係から明白であ
る。Qが述語の集合である場合、この照会をIsDisjoint
(p.Q.)に展開することは容易であり、回答は、pがQにお
けるあらゆる述語と互いに素であれば、真である。

【００３１】IsSuperset(p,q): pの領域がqの領域の上
位集合であるかどうかを照会する。pからqへのエッジが
存在すれば、述語pは述語qの上位集合である。例えば、
図３のＡにおいて、p2はｐ5の上位集合である。

【００３２】IsComplement(p,q): pおよびqの領域が互
いに補集合であるかどうか照会する。述語pおよびqは、
それらの領域の和集合が既存の述語の和集合と等しけれ
ば、補集合であり、それらの領域の共通部分は空集合で
ある。

【００３３】LeastUpperBoundSum(p,Q): 述語集合Qに述
語pを加える計算結果の集合の領域は、pの領域およびQ
の領域の和集合の最小上位集合である。あるパーティシ
ョンの中の子述語のすべてがpおよびQの和集合に現れれ
ば、それら子述語はそれらの親述語と置き換えられるこ
とによって、上記計算結果の集合は簡略化される。

【００３４】LeastUpperBoundDiff(p,Q): 述語集合Qか
ら述語pを減ずる。計算結果の集合の領域は、pの領域に
よって減じられたQの領域の最小上位集合である。例え
ば、図３のＡにおいて、pxはLeastUpperBoundDiff(p5,p
2)と等しい。

【００３５】制御フローを分析するため、制御述語が基
本ブロックに割り当てられ、制御フロー切り替えおよび
合流ポイントにおいてパーティションが形成される。特
別の関心が下記の制御フロー構造に払われるとはいえ、
本発明の述語分析は、簡略不可能なグラフ、切り替え文
その他を含むいかなる任意の制御フロー・グラフをも取
り扱う。

【００３６】臨界エッジ−臨界エッジは、そのソースが
複数の後続ノードを持ち、その行き先が複数の先行ノー
ドを持つエッジとして定義される。例えば、図１のＡに
おいて、S2からS4へのエッジは臨界エッジである。切り
替え(合流)ポイントにおいて、臨界エッジは、パーティ
ションにおける子述語として行き先(ソース)ノードの制
御述語の使用を防ぐ。このことは、この臨界エッジ上
で、ソース・ノードが行き先ノードを支配しないためあ
るいは行き先ノードがソース・ノードを事後支配しない
ため、発生する。この問題を解決するため、本発明は、
臨界エッジ上にノードを概念的に作成し、暗黙的述語を
ノードに割り当てる。注：このエッジ分割は概念レベル
で行われるもので、ＣＦＧを実際に変えない。この仮想
エッジ分割によって、すべての先行ノードは切り替えポ
イントにおいてそれらの後続ノードを支配し、すべての
後続ノードは合流ポイントにおいてその先行ノードを事
後支配する。これによってパーティションの作成が単純
化される。注：ノードpがノードqを支配または事後支配
すれば、pはパーティション・グラフにおいて常にqの先
祖であり得る。

【００３７】バック・エッジ−バック・エッジはＣＦＧ
におけるサイクルを完了するエッジである。現在の技術
では、述語分析においてバック・エッジを考慮したとし
ても、述語に関して導出できる有用な情報は少ない。例
えば、ループにおいて囲われるif-then-else構造は、th
en-およびelse-節の両方が同じ繰り返しの中で実行され
ることはないが、別の繰り返しの中では実行される場合
がある。従って、この２つの節に割り当てられる述語
は、特定の繰り返しの範囲内では互いに素であるが、繰
り返し全体にわたって互いに素であるとは限らない。こ
の述語分析の結果は、バック・エッジを無視して割り込
まれる。これは、分析精度に対する影響をほとんど持た
ない。これは、ｉｆ変換がすでに非周期的な地域に制限
されているという事実に部分的による。パーティション
・グラフ構築の間、バック・エッジも、また、仮想ノー
ドをそれらに割り当てることによって、分割される。本
発明の分析は、簡略化不可能なグラフにも適用できる。
しかしながら、バック・エッジは簡略化不可能なグラフ
に対してむしろ恣意的に選択されるので、結果の精度は
あまり高くないかもしれない。

【００３８】図４は、制御述語に基づいてパーティショ
ン・グラフを構築するアルゴリズムを示す。入力はＣＦ
Ｇである。臨界エッジおよびバック・エッジに関する分
割が先ず実行される(ステップ４０１)。制御同等ノード
の検出(ステップ４０２)は正確性にとって不可欠のもの
ではないが、制御同等領域を持つノードが同じ述語にマ
ップされる(ステップ４０３)と述語分析の精度は向上す
る。すべてのプログラム切り替えおよび合流ポイントに
おいてパーティションを作成して(ステップ４０４およ
び４０５)、述語関係を追跡する。最後に(ステップ４０
６)、非開始ノードが親ノードを持っていなければ、パ
ーティションを作成し、そのノードをその最近接の支配
ノードに結合して、パーティション・グラフを完成させ
る。

【００３９】図１のＡのＣＦＧに基づいて図３のＡのパ
ーティション・グラフを構築する方法を以下記述する。
ｉｆ変換コードに基づいてパーティション・グラフを構
築する本発明の記述と同様に、(図１のＡの)ノードS1
は、ＣＦＧにおける開始ノードであり、その制御述語と
してp0を与えられる。ノードS6は、S1に対する制御同等
ノードであってp0を同様に割り当てられる。残りのノー
ドに割り当てられる制御述語(p2-p5)は図１のＡに示さ
れている。S1における切り替えポイントのため(図３の
Ａに符号で示されているように)パーティションａが作
成される。S2からS4へのエッジは臨界エッジであり、px
がこのエッジに割り当てられ、エッジ分割が実行され
る。パーティションbは、S2における切り替えポイント
であるので、作成される。パーティションcおよびdは、
S4およびS6における合流ポイントであるので、作成され
る。

【００４０】実体述語の間のローカルな関係を捕捉する
パーティション・グラフを構築する詳細を以下記述す
る。実体述語の間の関係は、比較(compare)命令のよう
な述語が定義されるポイントの各々において作成され
る。

【００４１】図５は、実体述語に関するパーティション
・グラフを構築するアルゴリズムを示す。実体述語を定
義する最も普通のケースは、無条件タイプを持つ比較命
令である(ステップ５０１)。図５において、親述語とし
てppを持ち、互いに素な子述語としてp1およびp2を持つ
パーティションが作成される。qpがp0であれば、基本ブ
ロックの制御述語であるbpによって現在命令はガードさ
れ、p1およびp2の領域の和集合はbpの領域であることが
観察される。従って、親述語として制御述語bpを持つパ
ーティションが構築される。この点は、制御述語と実体
述語の関係を確立して大域的視野からの述語分析を可能
にする上での鍵である。qpがp0でなければ、この命令が
実行されるかどうかに影響を与える制御条件のすべて
が、定義qpに統合されている。この点は本発明の実施に
おいて確認されている。従って、qpがp0でなければ、p1
およびp2の和集合はqpであり、p1およびp2をbpへ結合さ
せるパーティションを構築する必要はない。比較命令を
ガードする実際の述語(pp)の領域は、常に、bpの領域の
部分集合である。

【００４２】その他の３つのタイプの比較命令は、述語
の前の値が新しい述語に影響を及ぼすという形態での述
語更新を伴う。これらタイプの比較命令が頻繁に使用さ
れず、またパーティション・グラフによるモデル化が簡
単ではないので、本発明はそれらタイプの取り扱いに消
極的である。条件つきのタイプをもつ比較命令に関して
は、qpがp0であれば、この命令は実質的に無条件タイプ
であって、無条件タイプと同じ方法で取り扱う。qpがp0
でなければ、p1およびp2に単にヌルの述語ノードをマッ
プして、述語分析に対する照会の間それらは消極的方法
で取り扱われる。注：onおよびoc(またはanおよびan)目
標述語の両方が比較命令に現れるならば、ただ１つの目
標が存在するかのようにそれらを分離して処理する。an
andタイプの比較命令に関しては、p1の領域は、常に、
p1_oldの領域の部分集合である。an orタイプの比較命
令に関しては、p1の領域は、常に、p1_oldの領域の上位
集合であって、p1を制御述語bpに結合するパーティショ
ンが作成され、パーティション・グラフが完成される。

【００４３】図４および図５に示される方法およびシス
テムに基づいて、図６のパーティション・グラフが構築
され、例(1)における述語に関する大域的関係が捕捉さ
れる。ｉｆ節を含む基本ブロックは、その制御述語とし
てp0を割り当てられ、パーティション・グラフのルート
となる。then節およびelse節はそれらの制御述語として
それぞれp_then節およびp_else節を割り当てられる。述
語の偽への初期化は、パーティション・グラフのにおい
て述語ノードを何も作成しない。if-then-else構造のた
め制御フローにおける切り替えポイントにおいてパーテ
ィションａが作成される。then節において実体述語pお
よびqを割り当てている比較命令のためパーティション
ｂが作成される。else節において実体述語rおよびsを割
り当てている比較命令のためパーティションｃが作成さ
れる。このパーティション・グラフは、p、q、rおよびs
が互いに素という大域的述語関係を追跡する。この関係
は、xおよびyが相互に干渉しないことを保証するために
必要である。

【００４４】本発明のｉｆ変換によって生成される比較
命令の２つの共通のパターンがある。プログラム切り替
えポイントに関して、cmpp.un.uc命令が生成され、図５
のシステムおよび方法(ステップ５０２)がこれを正確に
モデル化する。(しばしば臨界エッジによる)構造化され
ないプログラム合流ポイントに関して、mpp.un.ucおよ
びcmpp.on(またはcmpp.oc)命令の組み合わせが割り当て
られる。図５の中のアルゴリズムは常に正しいが、an o
rタイプの比較命令については消極的かもしれない。そ
の理由は、この初期の実施において、述語を制御する比
較条件が追跡されなかったしまた述語に番号付けの値が
与えられなかったためである。例えば、図１のＢのｉｆ
変換コードについて、番号付けの値がなければ、p3およ
びp4_1が同じ述語ノードにマップされることができるこ
とを認識できないし、p4_2がp4_1とpxの和集合であるこ
とを把握することはできない。しかしながら、このよう
なタイプの非構造化合流は、ｉｆ変換比較命令のわずか
な部分(本発明実施形態の経験では１０％以下)にすぎな
い。将来、an orタイプの比較命令の正確なモデル化が
行われるであろう。

【００４５】本発明およびその特長の詳細を以上記述し
たが、本発明の理念および範囲を逸脱することなく種々
の変更修正を行うことができる点は認められるべきであ
ろう。

【００４６】本発明には、例として次のような実施様態
が含まれる。 （１）複数の述語を持つ述語型コードを処理するシステ
ムであって、各述語に関する領域を決定する手段と、決
定した領域の各々を互いに素の部分集合に細分化する手
段と、述語の大域的関係を捕捉するため細分化された領
域の各々に基づいてパーティション・グラフを構築する
手段と、を備える述語型コード処理システム。 （２）各述語を細分化する上記手段が、制御述語を細分
化する手段を含む、上記（１）に記載の述語型コード処
理システム。 （３）制御述語を細分化する上記手段が、各臨界エッジ
および各バック・エッジに関する仮想ノードを作成する
ことによって臨界エッジおよびバック・エッジを分割す
る手段と、同等制御ノードを確認する手段と、同等制御
ノードの各集合に同一述語を割り当てる手段と、合流ポ
イントおよび切り替えポイントを持つノードに割り当て
られた述語にパーティションを形成する手段と、を含む
上記（２）に記載の述語型コード処理システム。 （４）制御述語を分割する上記手段が、先行ノードを持
たない非開始ノードにとって最近節の支配ノードの中に
パーティションを形成する手段を含む、上記（３）に記
載の述語型コード処理システム。 （５）制御述語を細分化する上記手段が、開始ノードに
対してその制御述語として述語p0を割り当てる手段を含
む、上記（３）に記載の述語型コード処理システム。

【００４７】（６）各述語を細分化する上記手段が、実
体述語を細分化する手段を含む、上記（１）に記載の述
語型コード処理システム。 （７）実体述語を細分化する上記手段が、比較命令を持
つノードに割り当てられた述語にパーティションを形成
する手段を含む、上記（６）に記載の述語型コード処理
システム。 （８）実体述語を細分化する上記手段が、述語を定義す
る定義命令を持つノードに割り当てられた述語にパーテ
ィションを形成する手段を含む、上記（６）に記載の述
語型コード処理システム。 （９）上記述語型コードが複数の基本ブロックに分割さ
れていて、該システムが、２つの基本ブロックが互いに
素であるか否かを判断する手段を更に備える、上記
（１）に記載の述語型コード処理システム。 （１０）上記述語型コードが複数の基本ブロックに分割
されていて、該システムが、１つの基本ブロックが別の
基本ブロックの上位集合であるか否かを判断する手段を
更に備える、上記（１）に記載の述語型コード処理シス
テム。 （１１）上記述語型コードが複数の基本ブロックに分割
されていて、該システムが、２つの基本ブロックが互い
に補集合であるか否かを判断する手段を更に備える、上
記（１）に記載の述語型コード処理システム。

【００４８】（１２）制御フロー・グラフ・コードに関
してｉｆ変換を実行してグラフ・コードにおける各命令
に関する述語を形成する手段を更に備える、上記（１）
に記載の述語型コード処理システム。 （１３）ｉｆ変換を実行する上記手段が、各領域を細分
化する上記手段の前に動作する、上記（１２）に記載の
述語型コード処理システム。 （１４）ｉｆ変換を実行する上記手段が、パーティショ
ン・グラフを構築する上記手段の後に動作する、上記
（１２）に記載の述語型コード処理システム。 （１５）上記領域が、述語型コードの基本ブロックを完
全に実行するために必要なすべてのトレースを含み、従
って、ある１つのトレースは、Ｐが真の時該トレースの
すべての命令が実行されるように、特定の述語pによっ
てガードされる命令集合である、上記（１）に記載の述
語型コード処理システム。 （１６）上記述語型コードが複数の基本ブロックに分割
されていて、該システムが、基本ブロックに関して制御
述語を作成する手段を更に備える、上記（１）に記載の
述語型コード処理システム。 （１７）述語コードの処理が、持続的データ構造の徐々
に増加する更新によって制約されずに、種々のフェーズ
のコンパイラ最適化ルーチンによって呼び出されること
ができる、上記（１）に記載の述語型コード処理システ
ム。

【００４９】（１８）複数の基本ブロックに分割された
コードを処理するシステムであって、各ブロックに関し
て領域を決定する手段と、決定した領域の各々を互いに
素な部分集合に細分化する手段と、述語の大域的関係を
捕捉するため細分化された領域の各々に基づいてパーテ
ィション・グラフを構築する手段と、を備える、コード
処理システム。 （１９）２つの基本ブロックが互いに素であるか否かを
判断する手段を更に備える、上記（１８）に記載のコー
ド処理システム。 （２０）１つの基本ブロックが別の基本ブロックの上位
集合であるか否かを判断する手段を更に備える、上記
（１８）に記載のコード処理システム。 （２１）２つの基本ブロックが互いに補集合であるか否
かを判断する手段を更に備える、上記（１８）に記載の
コード処理システム。

【００５０】（２２）複数の述語を持つ述語型コードを
処理する方法であって、各述語に関する領域を決定する
ステップと、決定した領域の各々を互いに素の部分集合
に細分化するステップと、述語の大域的関係を捕捉する
ため細分化された領域の各々に基づいてパーティション
・グラフを構築するステップと、を含む述語型コード処
理方法。 （２３）各述語を細分化する上記ステップが、制御述語
を細分化するステップを含む、上記（２２）に記載の述
語型コード処理方法。 （２４）制御述語を細分化する上記ステップが、各臨界
エッジおよび各バック・エッジに関する仮想ノードを作
成することによって臨界エッジおよびバック・エッジを
分割するステップと、同等制御ノードを確認するステッ
プと、同等制御ノードの各集合に同一述語を割り当てる
ステップと、合流ポイントおよび切り替えポイントを持
つノードに割り当てられた述語にパーティションを形成
するステップと、を含む上記（２３）に記載の述語型コ
ード処理方法。 （２５）制御述語を分割する上記ステップが、先行ノー
ドを持たない非開始ノードにとって最近節の支配ノード
の中にパーティションを形成するステップを含む、上記
（２４）に記載の述語型コード処理方法。 （２６）制御述語を細分化する上記ステップが、開始ノ
ードに対してその制御述語として述語p0を割り当てるス
テップを含む、上記（２４）に記載の述語型コード処理
方法。 （２７）各述語を細分化する上記ステップが、実体述語
を細分化するステップを含む、上記（２２）に記載の述
語型コード処理方法。 （２８）実体述語を細分化する上記ステップが、比較命
令を持つノードに割り当てられた述語にパーティション
を形成するステップを含む、上記（２７）に記載の述語
型コード処理方法。 （２９）実体述語を細分化する上記ステップが、述語を
定義する定義命令を持つノードに割り当てられた述語に
パーティションを形成するステップを含む、上記（２
７）に記載の述語型コード処理方法。

【００５１】（３０）上記述語型コードが複数の基本ブ
ロックに分割されていて、該方法が、２つの基本ブロッ
クが互いに素であるか否かを判断するステップを更に備
える、上記（２２）に記載の述語型コード処理方法。 （３１）上記述語型コードが複数の基本ブロックに分割
されていて、該方法が、１つの基本ブロックが別の基本
ブロックの上位集合であるか否かを判断するステップを
更に備える、上記（２２）に記載の述語型コード処理方
法。 （３２）上記述語型コードが複数の基本ブロックに分割
されていて、該方法が、２つの基本ブロックが互いに補
集合であるか否かを判断するステップを更に備える、上
記（２２）に記載の述語型コード処理方法。 （３３）制御フロー・グラフ・コードに関してｉｆ変換
を実行してグラフ・コードにおける各命令に関する述語
を形成するステップを更に備える、上記（２２）に記載
の述語型コード処理方法。 （３４）ｉｆ変換を実行する上記ステップが、各領域を
細分化する上記ステップの前に動作する、上記（３３）
に記載の述語型コード処理方法。 （３５）ｉｆ変換を実行する上記ステップが、パーティ
ション・グラフを構築する上記ステップの後に動作す
る、上記（３３）に記載の述語型コード処理方法。 （３６）上記述語型コードが複数の基本ブロックに分割
されていて、該方法が、基本ブロックに関して制御述語
を作成するステップを更に備える、上記（２２）に記載
の述語型コード処理方法。

【００５２】（３７）複数の述語を持ち、述語関係を大
域的に分析するため述語型コードを処理するシステムで
あって、各述語に関する領域を決定する手段と、決定し
た領域の各々を互いに素の部分集合に細分化する手段
と、述語の大域的関係を捕捉するため細分化された領域
の各々に基づいてパーティション・グラフを構築する手
段と、を備える述語型コード処理システム。 （３８）各述語を細分化する上記手段が、制御述語を細
分化する手段と、実体述語を細分化する手段と、を含
む、上記（３７）に記載の述語型コード処理システム。 （３９）制御述語を細分化する上記手段が、各臨界エッ
ジおよび各バック・エッジに関する仮想ノードを作成す
ることによって臨界エッジおよびバック・エッジを分割
する手段と、同等制御ノードを確認する手段と、同等制
御ノードの各集合に同一述語を割り当てる手段と、合流
ポイントおよび切り替えポイントを持つノードに割り当
てられた述語にパーティションを形成する手段と、先行
ノードを持たない非開始ノードにとって最近節の支配ノ
ードの中にパーティションを形成する手段と、開始ノー
ドに対してその制御述語として述語p0を割り当てる手段
と、を含む、上記（３８）に記載の述語型コード処理シ
ステム。 （４０）実体述語を細分化する上記手段が、比較命令を
持つノードに割り当てられた述語にパーティションを形
成する手段を含む、上記（３８）に記載の述語型コード
処理システム。

【００５３】

【発明の効果】本発明によって、述語の間の関係を大域
的に分析することが可能となり、それら関係を後続のコ
ンパイル分析または変換フェーズにおいてそれら述語関
係を照会すること可能となり、述語型コード開発の効率
が向上する。

【図面の簡単な説明】

【図１】Ａが制御フロー・グラフの１例を示し、Ｂがｉ
ｆ変換コードを示すブロック図である。

【図２】述語領域の間の集合関係を示すブロック図であ
る。

【図３】Ａが図１のＡの制御フローのパーティション・
グラフを示し、Ｂがその述語の領域を示すブロック図で
ある。

【図４】制御述語に関するパーティション・グラフ構築
の処理の流れ図である。

【図５】実体述語に関するパーティション・グラフ構築
の処理の流れ図である。

【図６】パーティション・グラフの１例を示すブロック
図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数の述語を持つ述語型コードを処理する
   システムであって、 各述語に関する領域を決定する手段と、 決定した領域の各々を互いに素の部分集合に細分化する
   手段と、 述語の大域的関係を捕捉するため細分化された領域の各
   々に基づいてパーティション・グラフを構築する手段
   と、 を備える述語型コード処理システム。