JPH0667868A - アルゴリズムを記号評価する方法およびアルゴリズムをトランスレートする装置 - Google Patents

Abstract

(57)【要約】 【目的】 ソフトウェアからハードウェアへの変換を可
能とするアルゴリズムの記号評価方法およびその装置を
提供すること。 【構造】 このアルゴリズムは、少なくとも一つの入力
データの値に依存した少なくとも一つの条件分岐ステー
トメントを有する。この方法は、アルゴリズムを複数の
ノード（各ノードは複数のステートメントのうちの少な
くとも一つを表す）を有する制御フローグラフに変換す
る工程を含む。この制御フローグラフは、データ依存性
条件付分岐ステートメントの各々に対し一つの条件付分
岐ノードを更に含む。次に複数のノードの各々に対する
逆ドミネータを計算し、これら逆ドミネータから各々の
条件付分岐ノードに対する合流点ノードを引き出す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的には記号のイン
タープリテイション技術の分野に関し、詳細にはデータ
依存性制御フローによりアルゴリズムを記号評価する方
法に関する。

【０００２】

【従来の技術】所定のデジタル信号処理（ＤＳＰ）アプ
リケーションを実現して必要な性能を得るのに、カスタ
ムデザインの集積回路が設計されることが多い。このこ
とは、一回のクロックサイクルで何回もの計算を行う並
列アーキテクチャを必要とするＤＳＰアプリケーション
に特に当てはまる。一般的にデザイナーはまずアルゴリ
ズムの試験台となるソフトウェアでＤＳＰアルゴリズム
を作成する。このＤＳＰアルゴリズムがソフトウェアで
充分にテストされ、デバッグされた後に、このアルゴリ
ズムはソフトウェアでの実現を忠実に再現するようハー
ドウェアで再度実現される。しかしながら、ハードウェ
アの設計で利用できるツールおよび基本ビルディングブ
ロックは異なるので、達成できるハードウェアの実現
は、ソフトウェアのプロトタイプとは、異なって機能し
たり、機能しなかったりすることがある。したがって、
再実現プロセスから生じるエラーを除くことができるよ
うソフトウェアの実現からハードウェアの実現を直接に
導くことができるトランスレータが望まれている。

【０００３】

【発明が解決しようとする課題】ソフトウェアからハー
ドウェアへのトランスレーションの達成を行う一つの方
法は、ソフトウェアのアルゴリズムをまずデータフロー
グラフにトランスレートすることであり、このデータフ
ローグラフからハードウェア回路を構成できる。トラン
スレーションの一つの技術として記号評価方法がある
が、この方法は部分的評価のコンパイル技術と関係して
いる。部分評価方法とは、既知の入力データを備えたプ
ログラムの部分を評価するもので、特定されていない入
力データを備えたプログラム部分は、実行時にしか評価
されない。従って、プログラムにデータ依存性がない場
合、プログラムは完全に評価できる。しかしながら、デ
ータに依存しないアルゴリズムはほとんど無い。例え
ば、ＩＦステートメントの条件またはＦＯＲループ上の
境界がある入力データに依存している場合、アルゴリズ
ムはデータ依存制御フローを有することになる。

【０００４】従来の記号評価方法は、データ依存制御フ
ローを備えたアルゴリズムを満足できるよう処理できな
い。従って、データ依存制御フローを備えたアルゴリズ
ムを記号評価する技術が望まれてきた。かかる技術は、
この技術をＤＰＳ用ハードウェアの設計に応用するのに
役立つだけでなく、コンパイラーによるプログラムの最
適化および並列化を利用するアプリケーションにも役立
つ。

【０００５】

【課題を解決するための手段および作用】本発明によれ
ば、従来技術に関連した欠点および問題を実質的に解消
または減少したデータ依存性制御フロー評価方法が提供
される。

【０００６】本発明の一つの様相によれば、アルゴリズ
ムを記号評価する方法が提供される。このアルゴリズム
は、少なくとも一つの入力データの値に依存した少なく
とも一つの条件分岐付ステートメントを有する。この方
法は、アルゴリズムを複数のノード（各ノードは複数の
ステートメントのうちの少なくとも一つを表す）を有す
る制御フローグラフに変換する工程を含む。この制御フ
ローグラフは、データ依存性条件付分岐ステートメント
の各々に対し一つの条件付分岐ノードを更に含む。次に
複数のノードの各々に対する逆ドミネータを計算し、こ
れら逆ドミネータから各々の条件付分岐ノードに対する
合流点ノードを引き出す。

【０００７】本方法は、更にアルゴリズムで参照される
すべての変数を含むシャドー記号表を作成し、かつ条件
付分岐ノードに応答してデータの各々の可能な値に対し
重複したシャドー記号表を作成するようになっている。
換言すれば、評価に達したとき条件付分岐ステートメン
トの各々の可能な分岐に対し、一つのシャドー記号表例
を作成する。

【０００８】本方法は、さらに制御フローに従って各ノ
ードを次々に記号的に評価し、シャドー記号表内の変数
の各々に一つの記号値を割り当てる。各々の分岐に対
し、データを各々の可能な値とし、シャドー記号表内の
変数の各々に記号値を割り当てることにより条件付分岐
ノードを評価する。各々の分岐は、その合流点ノードに
達するまで別々かつ次々に評価される。次に重複された
シャドー記号表がマージされ、別々の分岐に沿って異な
る記号値を得た各々の変数のを表す条件式となる。

【０００９】

【効果】本発明の重要な技術的効果としては、アプリケ
ーションアルゴリズムのソフトウェアでの実現をハード
ウェアでの実現、例えばカスタムアプリケーションの特
定集積回路（ＡＳＩＣ）へ置換トランスレートするため
のデータフローグラフに変換できるようデータ依存性制
御フローを除くための技術が得られることが挙げられ
る。

【００１０】本発明の別の重要な効果としては、コンパ
イラーによるプログラムの最適化および高度の並列化を
必要とするアプリケーションに有効な記号評価技術が得
られることが挙げられる。

【００１１】本発明の理解をより良好とするため、以下
添付図面を参照する。

【００１２】

【実施例】添付図面を参照すると、図１は特定のアプリ
ケーションのソフトウェアアルゴリズムの作成からハー
ドウェア回路を実現するためのトランスレーション方法
を示す略図である。これまで、回路デザイナーは、アプ
リケーションアルゴリズムをまずソフトウェアで作成し
ていた。このソフトウェアは、次にアルゴリズムの保全
性を保証するように充分にテストでき、デザイナーはそ
の後できるだけ忠実にソフトウェアを再現するようこの
アルゴリズムをハードウェアで再実現しなければならな
い。アーキテクタ上高度の並列性が必要とされる所定の
デジタル信号処理（ＤＳＰ）アプリケーションでは、ソ
フトウェアおよびハードウェアでのアプリケーションの
双方での実現が特に必要である。従って、このトランス
レーションプロセスは、テストされるソフトウェアのア
ルゴリズムをハードウェアで再実現する際にエラーの生
じやすいステップを除くことができる。

【００１３】第１図を参照すると、ソフトウェアの作成
は、高度のコンピュータ言語、例えばＣ言語およびフォ
ートランで一般に表現される。このソフトウェアの作成
は、次に記号評価方法２によりインタープリットされ、
この方法はソフトウェアの作成をデータフローグラフ３
で表す。このデータフローグラフ３から、アプリケーシ
ョンアルゴリズムのハードウェア回路の実現へと導くこ
とができる。

【００１４】ソフトウェアの作成は、ほとんど常にデー
タ依存性制御フローパスを含んでいるが、この制御フロ
ーパスは、トランスレーション方法における従来の記号
評価技術では取り扱いできない。本発明は、データ依存
性制御フローによるアルゴリズムの記号評価技術を提供
するものである。

【００１５】図２を参照すると、トランスレーション方
法の大半は、ブロック１０で開始する。ソフトウェア実
現コード１は、ブロック１２に示すようにＮ個のノード
を有する制御フローグラフにまず変換される。かかる制
御フローグラフ変換技術は、本明細書で引用するアルフ
レッド・ヴイ・エイホー（Ａｌｆｒｅｄ．Ｖ．Ａｈｏ）
外著、「コンパイラー、原理、技術およびツール（Ｃｏ
ｍｐｉｌｅｒｓ，Ｐｒｉｎｃｉｐｌｅｓ，Ｔｅｃｈｎｉ
ｑｕｅｓ ａｎｄ Ｔｏｏｌｓ）」に述べられているよ
うなコンパイラー設計およびコード最適化分野において
は従来技術となっている。この変換方法は、一般にデー
タフローグラフを含むデータ構造、例えばツリー構造を
組み立てる。概念的には、このデータフローグラフは、
ノードを含み、各ノードが、ソフトウェアアルゴリズム
からの内部分岐のない実行可能なステートメントの組を
含む。

【００１６】Ｃ＋＋言語で書かれた次のソフトウェアコ
ード例を参照しても本技術が良好に理解されよう。

【００１７】

【数１】

【００１８】図３に例Ａ内のアルゴリズムの制御フロー
グラフを示す。図３中の制御フローグラフは、４つのノ
ード３６〜４０を示す。ノード３６で、条件式内の変数
ｃが真すなわち非ゼロであれば制御はノード３７へフロ
ーし、変数ｉには変数ｙの値が割り当てられる。一方、
変数ｃがゼロであれば、ノード３８にフローし、このノ
ード３８で変数ｉに変数ｘの値が割り当てられる。ノー
ド４０では、変数ｉの値にリターンされる。したがっ
て、例Ａは条件式を有し、その値ｉは入力ｃに依存して
いるので、ノード３６は条件付分岐ノードとなることが
判る。

【００１９】次に図２のブロック１６に移る。ここでは
ブロック１２で得た制御フローグラフから逆ドミネータ
を計算する。所定ノードの逆ドミネータは、ノードの組
として定義され、制御ステップはこの所定ノードからこ
れらのノードの組を通過するよう保証されている。ノー
ドＮと最終ノードｎｏの組を備えた制御フローグラフの
逆ドミネータを見つけるための疑似コードアルゴリズム
は次の通りである。

【００２０】

【数２】各ｎ∈Ｎに対し、 Ｒ（ｎ）：＝Ｎ； Ｒ（ｎｏ）：＝｛ｎｏ｝； Ｒ（ｎ）へ変わる間に、Ｎ内のｎに対し、

【００２１】ここでＲ（ｎ）はノードｎの逆ドミネータ
の組であり、ｓｕｃ（ｎ）はノードｎのサクセッサの組
である。一つのノードｎのサクセッサは、実行フロー内
のノードｎのサクセッサは、実行フロー内のノードｎの
直接後に続くノードの組と定義される。例えば、図３内
のノード３６のサクセッサはノード３７および３８であ
る。上記アルゴリズム（１）が続けば、例Ａに対する逆
ドミネータは次の通りである。

【００２２】

【数３】

【００２３】ここでＲ（ｎ）は、ノードｎに対する逆ド
ミネータの組であり、Ｎは｛３６、３７、３８、４０｝
を含む。各々のノードに対し、逆ドミネータの組はそれ
自身を含んでいることが判る。

【００２４】図２中のブロック１８に進む。逆ドミネー
タの組から合流点を計算する。一つのノードが２つ以上
のサクセッサノードを有している場合すなわち条件付分
岐１である場合、合流点を逆ドミネータしているが、条
件付分岐ノード自体を排除しているノードから合流点ノ
ードを計算する。特定の条件付分岐ノードを計算する。
特定の条件付分岐ノードに対する逆ドミネータの残りに
より逆ドミネートされている逆ドミネータは、その条件
付分岐ノードに対する合流点となる。条件付分岐ノード
ｎに対する合流点を計算するための疑似コードアルゴリ
ズムは、次のように与えられる。

【００２５】

【数４】 候補点 ：＝Ｒ（ｎ）−｛ｎ｝： 合流点 ：＝候補点のうちのいくつか 候補点−｛合流点｝内のいくつかに対し、合流点∈Ｒ
（ｎ）であれば、合流点：＝ｎ；とする。従って、ノー
ド４０は図３中内の条件付ノード３６に対する合流点と
なる。

【００２６】ブロック１８内で合流点が計算されると、
準備ステップが完了し、ブロック２０内で記号評価方法
が開始する。ブロック２０に示すようにシャドー記号表
と称されるデータ構造が構成される。シャドー記号表の
代表例は次の通りである。

【００２７】

【表１】

【００２８】このシャドー記号表は、アーギュメント、
静的変数および大域変数に対するエントリを含む。エン
トリには変数を表す記号値が割り当てられる。エントリ
にたいする記号値は、ストリングとして示されるが、有
向非同期グラフとして実施することが好ましい。

【００２９】この点では、制御フローグラフ（ＣＦＧ）
内のノードは、図２中のブロック２１に示すように次々
にインタープリットされる。記号評価のための開始ノー
ドは、制御フローグラフの初期ノードとして、すなわち
ノード４０としてセットされている。

【００３０】ブロック２２では、終了ノードがこのとき
はノード４０に達しているか否か判別する。終了ノード
４０に達していなければ、ノード２３まで進み、このノ
ードでそのときのノードは条件付分岐ノードであるか否
か判別する。ノード３６は変数ｃの値に応じてノード３
７またはノード３８のいずれかを実施するデータ依存性
分岐式を含んでいるので、次にブロック２５を実施す
る。

【００３１】この点では、条件付分岐ノードの各分岐を
インタープリテイションのための実行準備ができてい
る。条件付分岐ノードｎの各々のサクセッサノードに対
し、シャドー記号表の重複例を作成し、各々の分岐のノ
ードを記号的に評価し、ここで開始ノードをノードｎに
変更し、終了ノードを条件付分岐ノードに対する合流点
に変更する。したがって、合流点に達するまで各分岐内
のノードごとに記号評価を行う。よって、各分岐のイン
タープリテイションを表すよう分岐ごとのシャドー記号
表を変える。例Ａでは、シャドー記号表の２つの例を構
成する。合流点ノード４０までに各条件式分岐を評価
し、それぞれのシャドー記号表内にそれらの結果を記録
する。例えばノード３７の式に指示されているように変
数ｉがインタープリットされ、”ｙ”の値が割り当てら
れる。この割り当て完了時にノード４０すなわち合流点
に達するので、真の分岐のインタープリテイションが完
了する。真の分岐のインタープリテイションの終了時の
シャドー記号表は、次の通りである。

【００３２】

【表２】

【００３３】同様にして、例Ａのデータフローグラフの
偽分岐に対するシャドー記号表を作成できる。

【００３４】

【表３】

【００３５】合流点すなわちノード４０に達すれば、偽
分岐のインタープリテイションが完了する。この点で
は、ブロック２５（図２）内の再帰インタープリテイシ
ョンが完了し、ブロック２６に進む。ブロック２６で
は、すべての分岐のシャドー記号表がマージされ表内の
対応する式が異なる条件式が得られる。例Ａでは、双方
の条件付分岐のインタープリテイションは、合流点ノー
ド４０に達しているので、表Ｂと表Ｃの結果は次のよう
にマージされる。

【００３６】

【表４】

【００３７】変数ｉの値は、ｃ言語の３部構成条件式に
より表される。

【００３８】

【数５】

【００３９】ここで、ｅ１が非ゼロすなわち真のとき式
は値２となり、ｅ１がゼロすなわち偽のとき、式はｅ３
となる。従って変数ｉの値は、条件の値ｃが非ゼロのと
き、変数ｙの値に等しく、ｃの値がゼロのとき変数ｘの
値に等しい。図２中のブロック３０では、条件式（ｃ？
ｙ：ｘ）にリターンする。

【００４０】例Ａでは、条件付分岐ノードは２つのサク
セッサノードしか有していない。すなわち真分岐と偽分
岐しか有していないので、本発明の好ましい実施態様
は、マルチ分岐に関連する条件付分岐ステートメント、
例えばｃ言語のスイッチステートメントにも同様に適用
できる。３部構成式を拡張してマルチ分岐化を実現する
ような式を容易に考案できる。

【００４１】本例に戻ると、式（ｃ？ｙ：ｘ）を供給す
ることにより、先のデータ依存性アルゴリズムの制御フ
ローを完全に除き、最大の可能な並列化を実現する。デ
ータ依存性条件付分岐は条件式まで減少され、これらの
条件式は全アプリケーションアルゴリズム用の最終デー
タフローグラフに容易に組み込むことができる。本発明
をさらによく理解できるようにするためさらに別の例を
挙げる。図４は、ループ構造の記号解釈をデモンストレ
ートする次のアルゴリズムのための代表的制御フローグ
ラフである。

【００４２】

【数６】

【００４３】制御フローグラフは、ノード４２〜４６を
含む。図２中でアウトラインを示したステップの後で、
逆ドミネータを計算する。アルゴリズム４１により計算
され、得られた逆ドミネータは次のとおりである。

【００４４】

【数７】

【００４５】ブロック１８に示すように上記アルゴリズ
ム（２）を使用して各条件付分岐ノード４３および４４
に対する合流点を計算する。ノード４３に対し、これ自
体を除く逆ドミネータはノード４７だけである。従っ
て、ノード４７はノード４３内の条件付分岐に対する合
流点である。ノード４４に対し、ノード４６が合流点と
なる。

【００４６】（図２中のブロック２０に示すように）次
のようにシャドー記号表を作成することにより記号評価
が進行する。

【００４７】

【表５】

【００４８】次にノード４２で開始して記号評価が進行
する。ノード４２内の２つの割り当てステートメントを
インタープリットすると、その結果次のシャドー記号表
が得られる。

【００４９】

【表６】

【００５０】次に、ノード４３内で最初の条件付分岐に
合流する。条件式（ｉ＜３）は変数ｉを含み、この値は
既知であるので、この式はデータ依存性条件付分岐では
ない。ｉはこのとき１であるので、ノード４４に進む
と、ここでデータ依存性条件付分岐に合う。ノード４４
は、条件（ａ［ｉ］＞ｂ）（変数ｂは”ａ［０］”に等
しくなるようセットされているので、この条件はシャド
ー記号表では”ａ［１］＞ａ［０］”となる）に依存し
た条件付分岐ノードである。条件”ａ［０］＞ａ
［０］”は、シャドー記号表をマージするとき使用され
る。

【００５１】条件（ａ［ｉ］＞ａ［０］）はデータに依
存しているので、合流点ノード４６に達するまで各分岐
をインタープリットする。このことは、図２中のブロッ
ク２５内の実施に対応する。（ａ［ｉ］＞ａ［０］）の
真条件の結果、シャドー記号表が得られる。

【００５２】

【表７】

【００５３】偽条件に対し、変数ｂの値は変わらないの
で、その結果得られるシャドー記号表は表Ｆと同じとな
るノード４６、すなわち合流点では、分岐”ａ［１］＞
ａ［０］”の条件を次のように使用するループを最初に
繰り返すようシャドー記号表ＦおよびＧをマージする。

【００５４】

【表８】

【００５５】合流点からインタープリテイションを進
め、変数ｉの値をノード４６で１だけ増加する。

【００５６】

【表９】

【００５７】ノード４３まで実行を進め、ここで条件付
分岐を評価する。この条件は真であるので、データ依存
性条件付分岐ノードであるノード４４に実行を進める。
ノード４４は、条件（ａ［ｉ］＞ｂ）に依存する条件付
分岐ノードであり、この条件はシャドー記号表のコンテ
キスト中では次のようになっている。

【００５８】

【数８】

【００５９】図２中のブロック２５に示すように、各分
岐に対しシャドー記号表の一列を作成し、その値をイン
タープリットする。偽分岐に対し、シャドー記号表内の
値は変わらない。真分岐に対し、シャドー記号表は次の
とおりである。

【００６０】

【表１０】

【００６１】ノード４５で、シャドー記号表ＩおよびＪ
をマージする。これらの表は、変数ｂの値が異なってい
るだけであるので、マージステップではこの値だけを変
える。条件付分岐における条件は、条件式内のセレクタ
として使用されるので、この結果次のシャドー記号表が
得られる。

【００６２】

【表９】

【００６３】ノード４６を再び評価するとき、変数ｉの
値を３に増加する。再度ノード４３まで実行を戻す。其
のときｉは３であり、３以上であるので、条件が偽とな
ったノード４３をインタープリットする。従って、ノー
ド４７まで実行を進める。ここでは変数ｂの値はシャド
ー記号表Ｋに示すように次のとおりである。

【００６４】

【数９】

【００６５】本例は、指向非同期グラフに式を残す利点
を示す。上記変数ｂの値は、サブ式”（ａ［１］＞ａ
［０］？ａ［１］：ａ［０］”を２回含み、この式はツ
リー構造の一つの式で経済的に示すことができる。

【００６６】最終例は繰り返し回数がデータに依存して
いるループに適用した本例を示す。このアルゴリズム例
は下記のとおりであり、図５に対応する制御フローグラ
フをしめす。

【００６７】

【数１０】

【００６８】図５に示すように、例Ｃの制御フローグラ
フはノード５０〜５６を含み、このうちのノード５１、
５２および５４は条件付分岐ノードである。

【００６９】図２にノンアウトラインを示したステップ
の後にブロック１６で次の結果を用い、上記アルゴリズ
ム（１）に従い逆ドミネータを計算する。

【００７０】

【数１１】

【００７１】ブロック１８では、上記アルゴリズム
（２）に従って、逆ドミネータからノード５１、５２お
よび５４に対する合流点を計算する。ノード５１に対し
ては、合流点はノード５６であり、ノード５２に対して
は、合流点はノード５４であり、ノード５４に対して合
流点はノード５６である。

【００７２】アーギュメント、静的変数および大域変数
およびそれぞれの記号値を含むシャドー記号表を作成す
ることにより例Ｃのアルゴリズムの記号評価が始まる。
次に制御フローグラフの第１ノードすなわちノード５０
で開始させて記号評価を進める。ノード５０での割り当
て式の後で、シャドー記号表は次のようになる。

【００７３】

【表１２】

【００７４】ノード５１には条件式があり、この値は既
知の値だけに依存しているので、この条件を評価する。
このとき変数ｉは３未満であるので、ノード５２まで実
行を進める。ノード５２は”ａ［１］＞ａ［０］”と翻
訳されているデータ依存性条件式（ａ［ｉ］＞ｂ）を含
んでいる。従って、２例のシャドー記号表を作成し、合
流点に達するまで条件付分岐のうちの各分岐を別々に評
価する。この条件の偽分岐の結果、変わっていないシャ
ドー記号表が得られるが、真分岐の結果、次の変わって
いない表が得られる。

【００７５】

【表１４】

【００７６】合流点であるノード５４では、２例のシャ
ドー記号表をマージする。シャドー記号表ＬおよびＭ
は、変数ｂの値が異なっているだけである。条件付分岐
内の条件は、条件式のセレクタとして使用され、次の表
を与える。

【００７７】

【表１４】

【００７８】ノード５４をインタープリットすると、こ
のノードは別のデータ依存性条件付分岐として認識され
る。ノード５４は、条件（ａ［ｉ］＞１０）に依存して
おり、この条件は現在のシャドー記号表のコンテキスト
ではデータ依存性条件（ａ［ｉ］＞１０）となってい
る。この条件はデータ依存性であるのでその分岐は次々
にインタープリットしなければならない。

【００７９】例ｃは、本技術の重要な様相を示す。ノー
ド５４内のデータ依存性分岐は、ループ構造内にあるの
で、このノードの偽分岐は、合流点ノード５６に達する
前にノード５４内のデータ依存性条件に達する。本例で
はインタープリタはノード５６の合流点に達するまでそ
の後の条件付分岐を反復して評価し、偽分岐の結果を生
じる。この点では、ノード５４内の元の条件付分岐の２
つのパスが合流点ノード５６に達し、マージできる。本
例は、２回深く反復するだけであるが、更に繰り返しを
必要とするデータ依存性分岐を含むループを制御フロー
グラフが有しているとき、この技術は任意の反復深さに
も適用できる。例えば、例Ｃのアルゴリズムのノード５
１内の条件を（ｉ＜１０）に変更したと仮定すれば、こ
の方法は、９の深さに反復する。

【００８０】ノード５４を評価すると、シャドー記号表
の重複例が作成される。条件（ａ［１］＞１０）の真分
岐は、すぐに合流点（ノード５６）に至るので、シャド
ー記号表は変わらないままである。他方、ノード５４内
の条件の偽分岐はノード５５進み、変数ｉの値をインク
リメントすることによりシャドー記号表を変える。

【００８１】

【表１５】

【００８２】ノード５１に進み、この中が真条件であれ
ばノード５２に進む。ノード５２はデータ依存性条件付
分岐を含んでいるので、シャドー記号表０の別の２つの
例が作成され、合流点（ノード５４）に達するまで各分
岐を評価する。ノード５２は次の式の値に依存してい
る。

【００８３】

【数１２】

【００８４】条件付分岐ノード５１の偽分岐はシャドー
記号表を変えることなくすぐに合流点ノード５６に進
み、一方真分岐は変数ｂに”ａ［２］”の値を割り当て
る。

【００８５】

【表１６】

【００８６】合流点（ノード５４）で、シャドー記号表
（表０およびＰ）の２例をマージすると、その結果得ら
れるシャドー記号表は次のようになる。

【００８７】

【表１７】

【００８８】ノード５４を評価するとき、データ依存性
条件式（ａ［２］＞１０）は、別の分岐評価を必要とす
る。ここでは、元の条件付分岐ノード５４の偽分岐をま
だ評価していることに留意されたい。ノード５４は、シ
ャドー記号表のコンテキスト内で値が（ａ［２］＞１
０）となっている条件に依存しているので条件付分岐で
ある。合流点ノード５６まで真分岐および偽分岐の双方
が評価され、マージされる。真分岐は、シャドー記号表
を変えることなく直接合流点までジャンプする。偽分岐
は、ノード５５内の変数ｉをまずインクリメントし、次
にノード５１内のデータ依存性条件をジャンプする。変
数ｉの値が異なっているだけの結果をマージすると、こ
の結果得られるシャドー記号表は、次のようになる。

【００８９】

【表１８】

【００９０】ノード５４の偽分岐のインタープリテイシ
ョンにより合流点すなわちノード５６に達するので、真
分岐に対するシャドー記号表、表Ｎは偽分岐に対するシ
ャドー記号表、表Ｒとマージされる。この結果得られる
シャドー記号表は次のとおりになる。

【００９１】

【表１９】

【００９２】従って、ノード５６に達すると、上記表Ｓ
に示されるような変数ｂの値がリターンされる。本発明
は、大域変数の条件式およびリターンステートメントで
明らかにリターンされる大域変数の条件式のリターン操
作に関係している。更に条件付分岐内にリターンステー
トメントが埋め込まれた合流点を計算するコンテキスト
で、リターンステートメントを制御フローグラフ内のユ
ニークな出口ノードへの潜在的分岐として扱う。このよ
うに実現することにより合流点を有するよう全ての条件
付分岐を保証する。

【００９３】以上で本発明を詳細に説明したが、特許請
求の範囲に示した本発明の精神および範囲から逸脱する
ことなく種々の変更、置換、改変が可能であると理解さ
れたい。

【００９４】以上の説明に関してさらに以下の項を開示
する。

【００９５】（１）複数の変数の値を操作する複数のス
テートメントを有し、更にデータ依存条件の値に依存す
る少なくとも一つの条件付分岐化ステートメントを有す
るアルゴリズムを記号評価する方法であって、開始ノー
ドおよび終了ノードおよび複数のノード（各ノードは前
記複数のステートメントのうちの少なくとも一つを示
す）を有し、前期データ依存性条件付分岐化ステートメ
ント用の条件付分岐ノードを含む制御フローグラフに前
記アルゴリズムを変換し、前記複数のノードの各々に対
する逆ドミネータの組を計算し、前記逆ドミネータに応
答して各々の条件付分岐ノードに対する合流点ノードを
引き出し、前記変数に対する記号値を有するシャドー記
号表を作成し、制御フローにしたがって各ノードを次々
に評価して前記シャドー記号表内の前記変数に記号値を
割り当て、前記条件付分岐ノードを評価し、前記条件付
分岐ノードに応答して前記データ依存性条件の各々の可
能な値にたいして重複したシャドー記号表を作成し、前
記データ依存性条件の各々の可能な値を仮定して、前記
重複したシャドー記号表内の各々の前記変数に記号値を
割り当て、前記合流点に達するまで前記条件付分岐化ス
テートメントの各分岐内に含まれるノードの評価を続
け、各前記合流点ノードで前記重複したシャドー記号表
をマージし、すべての条件付分岐の評価を完了して、前
記制御フローグラフの前記終了ノードに達し、前記アル
ゴリズムを示す条件式を与えるステップから成るアルゴ
リズムを記号評価する方法。

【００９６】（２）前記制御フローグラフ変換ステップ
は、前記終了ノードがサクセッサノードを有していない
場合、前記複数のノードの各々に対し、サクセッサノー
ドのリストを与えるステップを含む第１項記載の方法。

【００９７】（３）前記逆ドミネータを計算するステッ
プは、各ノード自体を含む前記制御フローグラフ内に前
記ノードのすべてを含むよう各ノードに対する逆ドミネ
ータ候補点の一組を初期化し、前記終了ノード自体のみ
を含むよう前記終了ノードに対する逆ドミネータ候補点
の組を改変し、その逆ドミネータ候補点の組とそのサク
セッサノードのすべての逆ドミネータ候補点の組との論
理積を演算し、ノード自体を追加し、その結果得られる
逆ドミネータ候補点の組を発生し、前記逆ドミネータ候
補点の組に変化が生じなくなるまで上記ステップを繰り
返すと共に各ノードに対する逆ドミネータの組を発生す
ることから成る第２項記載の方法。

【００９８】（４）条件付分岐ノードに対する合流点ノ
ードを引き出すステップは、組内の他のすべての逆ドミ
ネータによりドミネートされている逆ドミネータを、ノ
ード自体を除く逆ドミネータの組から選択するステップ
を含む第３項記載の方法。

【００９９】（５）前記マージをするステップは、次の
３部構成条件式

【０１００】

【数１３】

【０１０１】（ここで、ｅ１は条件付分岐ノードのデー
タ依存性条件で、ｅ２は条件が真の場合の変数の値であ
り、ｅ３は条件が偽の場合の変数の値である）を使用
し、ｅ１をデータ依存性条件に置換し、ｅ２を前記デー
タ依存性条件に対し偽条件となる前記重複シャドー記号
表内の変数に割り当てられた記号値に置換し、ｅ３を前
記データ依存性条件に対し偽条件となる前記重複シャド
ー記号表内の変数に割り当てられた記号値に置換するこ
とから成る第１項記載の方法。

【０１０２】（６）前記マージするステップは、前記重
複したシャドー記号表内の前期変数の値を組み合わせ、
前記データ依存性条件の各々の可能な値に対し変数が前
記値となる時を特定することから成る第１項記載の方
法。

【０１０３】（７）データ依存性条件の値に応じて変数
に異なる値を割り当てる少なくとも２との分岐に至る少
なくとも一つの条件付分岐化ステートメントを有するア
ルゴリズムをトランスレートする装置であって、複数の
ノード（このノードの一つは前記条件付分岐ノードを示
す）を有する制御フローグラフに前記アルゴリズムを変
換するための手段と、前記複数のノードの各々に対し逆
ドミネータの組を計算するための手段と、前記条件付分
岐化ステートメントの前記分岐が収束する合流点ノード
を前記計算された逆ドミネータに応答して引き出すため
の手段と、前記条件式および前記変数を有するシャドー
記号表を作成するための手段と、前記制御フローグラフ
内の各ノードを次々に記号評価するための手段と、前記
条件付分岐化ノードを評価すると共に前記データ依存性
条件の各々の可能な値を取ることにより前記条件付分岐
ノードの評価に応答して前記条件付分岐ノードの各分岐
に対する前記シャドー記号表の一つの例を作成するため
の手段と、前記合流点ノードに達するまで前記条件付分
岐化ステートメントの各分岐の評価に応答して前記シャ
ドー記号表の前記それぞれの例内の前記変数に記号値を
割り当てるための手段と、前記合流点ノードに達した時
に前記シャドー記号表の前記例をマージするための手段
と、すべての条件付分岐の評価を続け、前記制御フロー
グラフの前記終了ノードに達するための手段と、前記ア
ルゴリズムを表す条件式を与えるための手段とから成る
アルゴリズムをトランスレートするための装置。

【０１０４】（８）前記制御フローグラフを変換するた
めの前記手段は、前記複数のノードの各々に対するサク
セッサノードおよびサクセッサノードを有しない終了ノ
ードのリストを与えるための手段を含む第７項記載の装
置。

【０１０５】（９）前記逆ドミネータ計算手段は、各ノ
ード自体を含む、前記制御フローグラフ内の前記ノード
のすべてを含むよう各ノードに対する逆ドミネータ候補
点の組を初期化する手段と、ノード自体を含むようサク
セッサノードを有しない前記終了ノードに対する逆ドミ
ネータ候補点の組を改変するための手段と、ノードごと
にその逆ドミネータの組とそのサクセッサノードのすべ
ての逆ドミネータの組との論理積を演算し、前記ドミネ
ータ候補点の組の変化が生じなくなるまで演算の結果得
られる逆ドミネータの組を発生し、ノードごとに逆ドミ
ネータの組を発生するための手段とから成る第８項記載
の装置。

【０１０６】（１０）合流点ノードを引き出すための手
段は、他のすべての逆ドミネータ候補点を逆ドミネート
している逆ドミネータを各ノードに対する逆ドミネータ
候補点の前記組から選択するための手段を含む、第９項
記載の装置。

【０１０７】（１１）前記マージする手段は、次の３部
構成条件式

【０１０８】

【数１４】

【０１０９】（ここで、ｅ１は条件付分岐ノードのデー
タ依存性条件で、ｅ２は条件が真の場合の変数の値であ
り、ｅ３は条件が偽の場合の変数の値である）を使用
し、ｅ１をデータ依存性条件に置換し、ｅ２を前記デー
タ依存性条件に対し偽条件となる前記重複シャドー記号
表内の変数に割り当てられた記号値に置換し、ｅ３を前
記データ依存性条件に対し偽条件となる前記重複シャド
ー記号表内の変数に割り当てられた記号値に置換する第
７項記載の装置。

【０１１０】（１２）前記マージする手段は、前記重複
したシャドー記号表内の前記変数の値を組み合わせ、前
記データ依存性条件の各々の可能な値に対し変数が前記
値となる時を特定するステップを含む第１１項記載の装
置。

【０１１１】（１３）アルゴリズムを記号評価する方法
が提供される。このアルゴリズムは、少なくとも一つの
入力データの値に依存した少なくとも一つの条件付分岐
ステートメントを有する。この方法は、アルゴリズムを
複数のノード（各ノードは複数のステートメントのうち
の少なくとも一つを表す）を有する制御フローグラフに
変換する工程を含む。この制御フローグラフは、データ
依存性条件付分岐ステートメントの各々に対し一つの条
件付分岐ノードを更に含む。次に複数のノードの各々に
対する逆ドミネータを計算し、これら逆ドミネータから
各々の条件付分岐ノードに対する合流点ノードを引き出
す。本方法は、更にアルゴリズムで参照されるすべての
変数を収容するシャドー記号テーブルを作成し、かつ条
件付分岐ノードに応答してデータの各々の可能な値に対
し重複したシャドー記号テーブルを作成するようになっ
ている。本方法は更に制御フローにしたがって各ノード
を次々に記号的に評価し、シャドー記号テーブル内の変
数の各々に一つの記号値を割り当てる。各々の分岐に対
し、データを各々の可能な値とし、シャドー記号表内の
変数の各々に記号値を割り当てることにより条件付分岐
ノードを評価する。各々の分岐内のノードは、その合流
点ノードに達するまで評価される。次に重複されたシャ
ドー記号表がマージされる。すべての条件付分岐が評価
され、制御フローグラフの終了点に達するまで記号評価
を続け、アルゴリズムを表す条件式を得る。

【図面の簡単な説明】

【図１】ソフトウェアでの実現をハードウェア回路の実
現にトランスレートするための方法を示す大幅に簡略化
した図。

【図２】本発明の好ましい実施例の簡略化したフローチ
ャート。

【図３】本発明を良好に理解するための図例となるアル
ゴリズムの代表的制御フローグラフ。

【図４】ループ構造を有するアルゴリズムの代表的制御
フローグラフ。

【図５】反復回数が入力データに依存するループ構造を
有するアルゴリズム代表的制御フローグラフ。

【符号の説明】

１ ソフトウェア実現コード ３ データフローグラフ ３６ 条件付ノード ４３、４６、４７ ノード ５１、５２、５４ 条件付分岐ノード ５６ 分岐点ノード ｃ、ｂ、ｉ、ｙ、ｘ 変数

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成５年３月２９日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】全文

【補正方法】変更

【補正内容】

【書類名】 明細書

【発明の名祢】 アルゴリズムを記号評価する方法およ
ひアルゴリズムをトランスレートする装置

【特許請求の範囲】

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的には記号のイン
タープリテイション技術の分野に関し、詳細にはデータ
依存性制御フロニによりアルゴリズムを記号評価する方
法に関する。

【０００２】

【従来の技術】所定のデジタル信号処理（ＤＳＰ）アプ
リケーションを実現して必要な性能を得るのに、カスタ
ムデザインの集積回路が設計されることが多い。このこ
とは、一回のクロックサイクルで何回もの計算を行う並
列アーキテクチャを必要とするＤＳＰアプリケーション
に特に当てはまる。一般的にデザイナーはまずアルゴリ
ズムの試験台となるソフトウェアでＤＳＰアルゴリズム
を作成する。このＤＳＰアルゴリズムがソフトウェアで
充分にテストされ、デバッグされた後に、このアルゴリ
ズムはソフトウェアでの実現を忠実に再現するようハー
ドウェアで再度実現される。しかしながら、ハードウェ
アの設計で利用できるツールおよび基本ビルディングブ
ロックは異なるので、達成できるハードウェアの実現
は、ソフトウェアのプロトタイプとは、異なって機能し
たり、機能しなかったりすることがある。したがって、
再実現プロセスから生じるエラーを除くことができるよ
うソフトウェアの実現からハードウェアの実現を直接に
導くことができるトランスレータが望まれている。

【０００３】

【発明が解決しようとする課題】ソフトウェアからハー
ドウェアへのトランスレーションの達成を行う一つの方
法は、ソフトウェアのアルゴリズムをまずデータフロー
グラフにトランスレートすることであり、このデータフ
ローグラフからハードウェア回路を構成できる。トラン
スレーションの一つの技術として記号評価方法がある
が、この方法は部分的評価のコンパイル技術と関係して
いる。部分評価方法とは、既知の入力データを備えたプ
ログラムの部分を評価するもので、特定されていない入
力データを備えたプログラム部分は、実行時にしか評価
されない。従って、プログラムにデータ依存性がない場
合、プログラムは完全に評価できる。しかしながら、デ
ータに依存しないアルゴリズムはほとんど無い。例え
ば、ＩＦステートメントの条件またはＦＯＲループ上の
境界がある入力データに依存している場合、アルゴリズ
ムはデータ依存制御フローを有することになる。

【０００４】従来の記号評価方法は、データ依存制御フ
ローを備えたアルゴリズムを満足できるよう処理できな
い。従って、データ依存制御フローを備えたアルゴリズ
ムを記号評価する技術が望まれてきた。かかる技術は、
この技術をＤＰＳ用ハードウェアの設計に応用するのに
役立つだけでなく、コンパイラーによるプログラムの最
適化および並列化を利用するアプリケーションにも役立
つ。

【０００５】

【課題を解決するための手段および作用】本発明によれ
ば、従来技術に関連した欠点および問題を実質的に解消
または減少したデータ依存性制御フロー評価方法が提供
される。

【０００６】本発明の一つの様相によれば、アルゴリズ
ムを記号評価する方法が提供される。このアルゴリズム
は、少なくとも一つの入力データの値に依存した少なく
とも一つの条件分岐付ステートメントを有する。この方
法は、アルゴリズムを複数のノード（各ノードは複数の
ステートメントのうちの少なくとも一つを表す）を有す
る制御フローグラフに変換する工程を含む。この制御フ
ローグラフは、データ依存性条件付分岐ステートメント
の各々に対し一つの条件付分岐ノードを更に含む。次に
複数のノードの各々に対する逆ドミネータを計算し、こ
れら逆ドミネータから各々の条件付分岐ノードに対する
合流点ノードを引き出す。

【０００７】本方法は、更にアルゴリズムで参照される
すべての変数を含むシャドー記号表を作成し、かつ条件
付分岐ノードに応答してデータの各々の可能な値に対し
重複したシャドー記号表を作成するようになっている。
換言すれば、評価に達したとき条件付分岐ステートメン
トの各々の可能な分岐に対し、一つのシャドー記号表例
を作成する。

【０００８】本方法は、さらに制御フローに従って各ノ
ードを次々に記号的に評価し、シャドー記号表内の変数
の各々に一つの記号値を割り当てる。各々の分岐に対
し、データを各々の可能な値とし、シャドー記号表内の
変数の各々に記号値を割り当てることにより条件付分岐
ノードを評価する。各々の分岐は、その合流点ノードに
達するまで別々かつ次々に評価される。次に重複された
シャドー記号表がマージされ、別々の分岐に沿って異な
る記号値を得た各々の変数のを表す条件式となる。

【０００９】

【効果】本発明の重要な技術的効果としては、アプリケ
ーションアルゴリズムのソフトウェアでの実現をハード
ウェアでの実現、例えばカスタムアプリケーションの特
定集積回路（ＡＳＩＣ）へ置換トランスレートするため
のデータフローグラフに変換できるようデータ依存性制
御フローを除くための技術が得られることが挙げられ
る。

【００１０】本発明の別の重要な効果としては、コンパ
イラーによるプログラムの最適化および高度の並列化を
必要とするアプリケーションに有効な記号評価技術が得
られることが挙げられる。

【００１１】木発明の理解をより良好とするため、以下
添付図面を参照する。

【００１２】

【実施例】添付図面を参照すると、図１は特定のアプリ
ケーションのソフトウェアアルゴリズムの作成からハー
ドウェア回路を実現するためのトランスレーション方法
を示す略図である。これまで、回路デザイナーは、アプ
リケーションアルゴリズムをまずソフトウェアで作成し
ていた。このソフトウェアは、次にアルゴリズムの保全
性を保証するように充分にテストでき、デザイナーはそ
の後できるだけ忠実にソフトウェアを再現するようこの
アルゴリズムをハードウェアで再実現しなければならな
い。アーキテクタ上高度の並列性が必要とされる所定の
デジタル信号処理（ＤＳＰ）アプリケーションでは、ソ
フトウェアおよびハードウェアでのアプリケーションの
双方での実現が特に必要である。従って、このトランス
レーションプロセスは、テストされるソフトウェアのア
ルゴリズムをハードウェアで再実現する際にエラーの生
じやすいステップを除くことができる。

【００１３】第１図を参照すると、ソフトウェアの作成
は、高度のコンピュータ言語、例えばＣ言語およびフォ
ートランで一般に表現される。このソフトウェアの作成
は、次に記号評価方法２によりインタープリットされ、
この方法はソフトウェアの作成をデータフローグラフ３
で表す。このデータフローグラフ３から、アプリケーシ
ョンアルゴリズムのハードウェア回路の実現へと導くこ
とができる。

【００１４】ソフトウェアの作成は、ほとんど常にデー
タ依存性制御フローパスを含んでいるが、この制御フロ
ーパスは、トランスレーション方法における従来の記号
評価技術では取り扱いできない。本発明は、データ依存
性制御フローによるアルゴリズムの記号評価技術を提供
するものである。

【００１５】図２を参照すると、トランスレーション方
法の大半は、ブロック１０で開始する。ソフトウェア実
現コード１は、ブロック１２に示すようにＮ個のノード
を有する制御フローグラフにまず変換される。かかる制
御フローグラフ変換技術は、本明細書で引用するアルフ
レッド・ヴイ・エイホー（Ａｌｆｒｅｄ．Ｖ．Ａｈｏ）
外著、「コンパイラー、原理、技術およびツール（Ｃｏ
ｍｐｉｌｅｒｓ，Ｐｒｉｎｃｉｐｌｅｓ，Ｔｅｃｈｎｉ
ｑｕｅｓ ａｎｄ Ｔｏｏｌｓ）」に述べられているよ
うなコンパイラー設計およびコード最適化分野において
は従来技術となっている。この変換方法は、一般にデー
タフローグラフを含むデータ構造、例えばツリー構造を
組み立てる。概念的には、このデータフローグラフは、
ノードを含み、各ノードが、ソフトウェアアルゴリズム
からの内部分岐のない実行可能なステートメントの組を
含む。

【００１６】Ｃ＋＋言語で書かれた次のソフトウェアコ
ード例を参照しても本技術が良好に理解されよう。

【００１７】

【数１】

【００１８】図３に例Ａ内のアルゴリズムの制御フロー
グラフを示す。図３中の制御フローグラフは、４つのノ
ード３６〜４０を示す。ノード３６で、条件式内の変数
ｃが真すなわち非ゼロであれば制御はノード３７へフロ
ーし、変数ｉには変数ｙの値が割り当てられる。一方、
変数ｃがゼロであれば、ノード３８にフローし、このノ
ード３８で変数ｉに変数ｘの値が割り当てられる。ノー
ド４０では、変数ｉの値にリターンされる。したがっ
て、例Ａは条件式を有し、その値ｉは入力ｃに依存して
いるので、ノード３６は条件付分岐ノードとなることが
判る。

【００１９】次に図２のブロック１６に移る。ここでは
ブロック１２で得た制御フローグラフから逆ドミネータ
を引算する。所定ノードの逆ドミネータは、ノードの組
として定義され、制御ステップはこの所定ノードからこ
れらのノードの組を通過するよう保証されている。ノー
ドＮと最終ノードｎｏの組を備えた制御フローグラフの
逆ドミネータを見つけるための疑似コードアルゴリズム
は次の通りである。

【００２０］ 【００２０］【数２】

【００２１】ここでＲ（ｎ）はノードｎの逆ドミネータ
の組であり、ｓｕｃ（ｎ）はノードｎのサクセッサの組
である。一つのノードｎのサクセッサは、実行フロー内
のノードｎのサクセッサは、実行フロー内のノードｎの
直接後に続くノードの組と定義される。例えば、図３内
のノード３６のサクセッサはノード３７および３８であ
る。上記アルゴリズム（１）が続けば、例Ａに対する逆
ドミネータは次の通りである。

【００２２】

【数３】

【００２３】ここでＲ（ｎ）は、ノードｎに対する逆ド
ミネータの組であり、Ｎは｛３６、３７、３８、４０｝
を含む。各々のノードに対し、逆ドミネータの組はそれ
自身を含んでいることが判る。

【００２４】図２中のブロック１８に進む。逆ドミネー
タの組から合流点を計算する。一つのノードが２つ以上
のサクセッサノードを有している場合すなわち条件付分
岐１である場合、合流点を逆ドミネータしているが、条
件付分岐ノード自体を排除しているノードから合流点ノ
ードを計算する。特定の条件付分岐ノードを計算する。
特定の条件付分岐ノードに対する逆ドミネータの残りに
より逆ドミネートされている逆ドミネータは、その条件
付分岐ノードに対する合流点となる。条件付分岐ノード
ｎに対する合流点を計算するための疑似コードアルゴリ
ズムは、次のように与えられる。

【００２５】

【数４】 候補点 ：＝Ｒ（ｎ）−｛ｎ｝： 合流点 ：＝候補点のうちのいくつか 候補点−｛合流点｝内のいくつかに対し、合流点∈Ｒ
（ｎ）であれば、合流点：＝ｎ；とする。従って、ノー
ド４０は図３中内の条件付ノード３６に対する合流点と
なる。

【００２６】ブロック１８内で合流点が引算されると、
準備ステップが完了し、ブロック２０内で記号評価方法
が開始する。ブロック２０に示すようにシャドー記号表
と称されるデータ構造が構成される。シャドー記号表の
代表例は次の通りである。

【００２７】

【表１】

【００２８】このシャドー記号表は、アーギュメント、
静的変数および大域変数に対するエントリを含む。エン
トリには変数を表す記号値が割り当てられる。エントリ
にたいする記号値は、ストリングとして示されるが、有
向非同期グラフとして実施することが好ましい。

【００２９】この点では、制御フローグラフ（ＣＦＧ）
内のノードは、図２中のブロック２１に示すように次々
にインタープリットされる。記号評価のための開始ノー
ドは、制御フローグラフの初期ノードとして、すなわち
ノード４０としてセットされている。

【００３０】ブロック２２では、終了ノードがこのとき
はノード４０に達しているか否か判別する。終了ノード
４０に達していなければ、ノード２３まで進み、このノ
ードでそのときのノードは条件付分岐ノードであるか否
か判別する。ノード３６は変数ｃの値に応じてノード３
７またはノード３８のいずれかを実施するデータ依存性
分岐式を含んでいるので、次にブロック２５を実施す
る。

【００３１】この点では、条件付分岐ノードの各分岐を
インタープリテイションのための実行準備ができてい
る。条件付分岐ノードｎの各々のサクセッサノードに対
し、シャドー記号表の重複例を作成し、各々の分岐のノ
ードを記号的に評価し、ここで開始ノードをノードｎに
変更し、終了ノードを条件付分岐ノードに対する合流点
に変更する。したがって、合流点に達するまで各分岐内
のノードごとに記号評価を行う。よって、各分岐のイン
タープリテイションを表すよう分岐ごとのシャドー記号
表を変える。例Ａでは、シャドー記号表の２つの例を構
成する。合流点ノード４０までに各条件式分岐を評価
し、それぞれのシャドー記号表内にそれらの結果を記録
する。例えばノード３７の式に指示されているように変
数ｉがインタープリットされ、”ｙ”の値が割り当てら
れる。この割り当て完了時にノード４０すなわち合流点
に達するので、真の分岐のインタープリテイションが完
了する。真の分岐のインタープリテイションの終了時の
シャドー記号表は、次の通りである。

【００３２】

【表２】

【００３３】同様にして、例Ａのデータフローグラフの
偽分岐に対するシャドー記号表を作成できる。

【００３４】

【表３】

【００３５】合流点すなわちノード４０に達すれば、偽
分岐のインタープリテイションが完了する。この点で
は、ブロック２５（図２）内の再帰インタープリテイシ
ョンが完了し、ブロック２６に進む。ブロック２６で
は、すべての分岐のシャドー記号表がマージされ表内の
対応する式が異なる条件式が得られる。例Ａでは、双方
の条件付分岐のインタープリテイションは、合流点ノー
ド４０に達しているので、表Ｂと表Ｃの結果は次のよう
にマージされる。

【００３６】

【表４】

【００３７】変数ｉの値は、ｃ言語の３部構成条件式に
より表される。

【００３８】

【数５】ｅ１？ｅ２：ｅ３

【００３９】ここで、ｅ１が非ゼロすなわち真のとき式
は値２となり、ｅ１がゼロすなわち偽のとき、式はｅ３
となる。従って変数ｉの値は、条件の値ｃが非ゼロのと
き、変数ｙの値に等しく、ｃの値がゼロのとき変数ｘの
値に等しい。図２中のブロック３０では、条件式（ｃ？
ｙ：ｘ）にリターンする。

【００４０】例Ａでは、条件付分岐ノードは２つのサク
セッサノードしか有していない。すなわち真分岐と偽分
岐しか有していないので、本発明の好ましい実施態様
は、マルチ分岐に関連する条件付分岐ステートメント、
例えばｃ言語のスイッチステートメントにも同様に適用
できる。３部構成式を拡張してマルチ分岐化を実現する
ような式を容易に考案できる。

【００４１】本例に戻ると、式（ｃ？ｙ：ｘ）を供給す
ることにより、先のデータ依存性アルゴリズムの制御フ
ローを完全に除き、最大の可能な並列化を実現する。デ
ータ依存性条件化分岐は条件式まで減少され、これらの
条件式は全アプリケーションアルゴリズム用の最終デー
タフローグラフに容易に組み込むことができる。本発明
をさらによく理解できるようにするためさらに別の例を
挙げる。図４は、ループ構造の記号解釈をデモンストレ
ートする次のアルゴリズムのための代表的制御フローグ
ラフである。

【００４２】

【数６】

【００４３】制御フローグラフは、ノード４２〜４６を
含む。図２中でアウトラインを示したステップの後で、
逆ドミネータを計算する。アルゴリズム４１により計算
され、得られた逆ドミネータは次のとおりである。

【００４４】

【数７】

【００４５】ブロック１８に示すように上記アルゴリズ
ム（２）を使用して各条件付分岐ノード４３および４４
に対する合流点を計算する。ノード４３に対し、これ自
体を除く逆ドミネータはノード４７だけである。従っ
て、ノード４７はノード４３内の条件付分岐に対する合
流点である。ノード４４に対し、ノード４６が合流点と
なる。

【００４６】（図２中のブロック２０に示すように）次
のようにシャドー記号表を作成することにより記号評価
が進行する。

【００４７】

【表５】

【００４８】次にノード４２で開始して記号評価が進行
する。ノード４２内の２つの割り当てステートメントを
インタープリットすると、その結果次のシャドー記号表
が得られる。

【００４９】

【表６】

【００５０】次に、ノード４３内で最初の条件付分岐に
合流する。条件式（ｉ＜３）は変数ｉを含み、この値は
既知であるので、この式はデータ依存性条件付分岐では
ない。ｉはこのとき１であるので、ノード４４に進む
と、ここでデータ依存性条件付分岐に合う。ノード４４
は、条件（ａ［ｉ］＞ｂ）（変数ｂは”ａ［０］”に等
しくなるようセットされているので、この条件はシャド
ー記号表では”ａ［１］＞ａ［０］”となる）に依存し
た条件付分岐ノードである。条件”ａ［０］＞ａ
［０］”は、シャドー記号表をマージするとき使用され
る。

【００５１】条件（ａ［ｉ］＞ａ［０］）はデータに依
存しているので、合流点ノード４６に達するまで各分岐
をインタープリットする。このことは、図２中のブロッ
ク２５内の実施に対応する。（ａ［ｉ］＞ａ［０］）の
真条件の結果、シャドー記号表が得られる。

【００５２】

【表７】

【００５３】偽条件に対し、変数ｂの値は変わらないの
で、その結果得られるシャドー記号表は表Ｆと同じとな
る。ノード４６、すなわち合流点では、分岐”ａ［１］
＞ａ［０］”の条件を次のように使用するループを最初
に繰り返すようシャドー記号表ＦおよびＧをマージす
る。

【００５４】

【表８】

【００５５】合流点からインタープリテイションを進
め、変数ｉの値をノード４６で１だけ増加する。

【００５６】

【表９】

【００５７】ノード４３まで実行を進め、ここで条件付
分岐を評価する。この条件は真であるので、データ依存
性条件付分岐ノードであるノード４４に実行を進める。
ノード４４は、条件（ａ［ｉ］＞ｂ）に依存する条件付
分岐ノードであり、この条件はシャドー記号表のコンテ
キスト中では次のようになっている。

【００５８】

【数８】 ”ａ［２］＞（ａ［１］＞ａ［０］）？ａ［１］：ａ［０］）”

【００５９】図２中のブロック２５に示すように、各分
岐に対しシャドー記号表の一列を作成し、その値をイン
タープリットする。偽分岐に対し、シャドー記号表内の
値は変わらない。真分岐に対し、シャドー記号表は次の
とおりである。

【００６０】

【表１０】

【００６１】ノード４５で、シャドー記号表ＩおよびＪ
をマージする。これらの表は、変数ｂの値が異なってい
るだけであるので、マージステップではこの値だけを変
える。条件付分岐における条件は、条件式内のセレクタ
として使用されるので、この結果次のシャドー記号表が
得られる。

【００６２】

【表１１】

【００６３】ノード４６を再び評価するとき、変数ｉの
値を３に増加する。再度ノード４３まで実行を戻す。其
のときｉは３であり、３以上であるので、条件が偽とな
ったノード４３をインタープリットする。従って、ノー
ド４７まで実行を進める。ここでは変数ｂの値はシャド
ー記号表Ｋに示すように次のとおりである。

【００６４】

【数９】

【００６５】本例は、指向非同期グラフに式を残す利点
を示す。上記変数ｂの値は、サブ式”（ａ［１］＞ａ
［０］？ａ［１］：ａ［０］”を２回含み、この式はツ
リー構造の一つの式で経済的に示すことができる。

【００６６】最終例は繰り返し回数がデータに依存して
いるループに適用した本例を示す。このアルゴリズム例
は下記のとおりであり、図５に対応する制御フローグラ
フをしめす。

【００６７】

【数１０】

【００６８】図５に示すように、例Ｃの制御フローグラ
フはノード５０〜５６を含み、このうちのノード５１、
５２および５４は条件付分岐ノードである。

【００６９】図２にノンアウトラインを示したステップ
の後にブロック１６で次の結果を用い、上記アルゴリズ
ム（１）に従い逆ドミネータを計算する。

【００７０】

【数１１】

【００７１】ブロック１８では、上記アルゴリズム
（２）に従って、逆ドミネータからノード５１、５２お
よび５４に対する合流点を計算する。ノード５１に対し
ては、合流点はノード５６であり、ノード５２に対して
は、合流点はトード５４であり、ノード５４に対して合
流点はノード５６である。

【００７２】アーギュメント、静的変数および大域変数
およびそれぞれの記号値を含むシャドー記号表を作成す
ることにより例Ｃのアルゴリズムの記号評価が始まる。
次に制御フローグラフの第１ノードすなわちノード５０
で開始させて記号評価を進める。ノード５０での割り当
て式の後で、シャドー記号表は次のようになる。

【００７３】

【表１２】

【００７４】ノード５１には条件式があり、この値は既
知の値だけに依存しているので、この条件を評価する。
このとき変数ｉは３未満であるので、ノード５２まで実
行を進める。ノード５２は”ａ［１］＞ａ［０］”と翻
訳されているデータ依存性条件式（ａ［ｉ］＞ｂ）を含
んでいる。従って、２例のシャドー記号表を作成し、合
流点に達するまで条件付分岐のうちの各分岐を別々に評
価する。この条件の偽分岐の結果、変わっていないシャ
ドー記号表が得られるが、真分岐の結果、次の変わって
いない表が得られる。

【００７５】

【表１３】

【００７６】合流点であるノード５４では、２例のシャ
ドー記号表をマージする。シャドー記号表ＬおよひＭ
は、変数ｂの値が異なっているだけである。条件付分岐
内の条件は、条件式のセレクタとして使用され、次の表
を与える。

【００７７】

【表１４】

【００７８】ノード５４をインタープリットすると、こ
のノードは別のデータ依存性条件付分岐として認識され
る。ノード５４は、条件（ａ［ｉ］＞１０）に依存して
おり、この条件は現在のシャドー記号表のコンテキスト
ではデータ依存性条件（ａ［ｉ］＞１０）となってい
る。この条件はデータ依存性であるのでその分岐は次々
にインタープリットしなければならない。

【００７９】例ｃは、本技術の重要な様相を示す。ノー
ド５４内のデータ依存性分岐は、ループ構造内にあるの
で、このノードの偽分岐は、合流点ノード５６に達する
前にノード５４内のデータ依存性条件に達する。本例で
はインタープリタはノード５６の合流点に達するまでそ
の後の条件付分岐を反復して評価し、偽分岐の結果を生
じる。この点では、ノード５４内の元の条件付分岐の２
つのパスが合流点ノード５６に達し、マージできる。本
例は、２回深く反復するだけであるが、更に繰り返しを
必要とするデータ依存性分岐を含むループを制御フロー
グラフが有しているとき、この技術は任意の反復深さに
も適用できる。例えば、例Ｃのアルゴリズムのノード５
１内の条件を（ｉ＜１０）に変更したと仮定すれば、こ
の方法は、９の深さに反復する。

【００８０】ノード５４を評価すると、シャドー記号表
の重複例が作成される。条件（ａ［１］＞１０）の真分
岐は、すぐに合流点（ノード５６）に至るので、シャド
ー記号表は変わらないままである。他方、ノード５４内
の条件の偽分岐はノード５５進み、変数ｉの値をインク
リメントすることによりシャドー記号表を変える。

【００８１】

【表１５】

【００８２】ノード５１に進み、この中が真条件であれ
ばノード５２に進む。ノード５２はデータ依存性条件付
分岐を含んでいるので、シャドー記号表０の別の２つの
例が作成され、合流点（ノード５４）に達するまで各分
岐を評価する。ノード５２は次の式の値に依存してい
る。

【００８３】

【数１２】 （ａ［２］＞（ａ［１］＞ａ［０］）？ａ［１］：ａ［０］）

【００８４】条件付分岐ノード５１の偽分岐はシャドー
記号表を変えることなくすぐに合流点ノード５６に進
み、一方真分岐は変数ｂに”ａ［２］”の値を割り当て
る。

【００８５】

【表１６】

【００８６】合流点（ノード５４）で、シャドー記号表
（表ＯおよびＰ）の２例をマージすると、その結果得ら
れるシャドー記号表は次のようになる。

【００８７】

【表１７】

【００８８】ノード５４を評価するとき、データ依存性
条件式（ａ［２］＞１０）は、別の分岐評価を必要とす
る。ここでは、元の条件付分岐ノード５４の偽分岐をま
だ評価していることに留意されたい。ノード５４は、シ
ャドー記号表のコンテキスト内で値が（ａ［２］＞１
０）となっている条件に依存しているので条件付分岐で
ある。合流点ノード５６まで真分岐および偽分岐の双方
が評価され、マージされる。真分岐は、シャドー記号表
を変えることなく直接合流点までジャンプする。偽分岐
は、ノード５５内の変数ｉをまずインクリメントし、次
にノード５１内のデータ依存性条件をジャンプする。変
数ｉの値が異なっているだけの結果をマージすると、こ
の結果得られるシャドー記号表は、次のようになる。

【００８９】

【表１８】

【００９０】ノード５４の偽分岐のインタープリテイシ
ョンにより合流点すなわちノード５６に達するので、真
分岐に対するシャドー記号表、表Ｎは偽分岐に対するシ
ャドー記号表、表Ｒとマージされる。この結果得られる
シャドー記号表は次のとおりになる。

【００９１】

【表１９】

【００９２】従って、ノード５６に達すると、上記表Ｓ
に示されるような変数ｂの値がリターンされる。本発明
は、大域変数の条件式およびリターンステートメントで
明らかにリターンされる大域変数の条件式のリターン操
作に関係している。更に条件付分岐内にリターンステー
トメントか埋め込まれた合流点を計算するコンテキスト
で、リターンステートメントを制御フローグラフ内のユ
ニークな出口ノードへの潜在的分岐として扱う。このよ
うに実現することにより合流点を有するよう全ての条件
付分岐を保証する。

【００９３】以上で本発明を詳細に説明したが、特許請
求の範囲に示した本発明の精神および範囲から逸脱する
ことなく種々の変更、置換、改変が可能であると理解さ
れたい。

【００９４】以上の説明に関してさらに以下の項を開示
する。

【００９５】（１）複数の変数の値を操作する複数のス
テートメントを有し、更にデータ依存条件の値に依存す
る少なくとも一つの条件付分岐化ステートメントを有す
るアルゴリズムを記号評価する方法であって、開始ノー
ドおよび終了ノードおよび複数のノード（各ノードは前
記複数のステートメントのうちの少なくとも一つを示
す）を有し、前期データ依存性条件付分岐化ステートメ
ント用の条件付分岐ノードを含む制御フローグラフに前
記アルゴリズムを変換し、前記複数のノードの各々に対
する逆ドミネータの組を計算し、前記逆ドミネータに応
答して各々の条件付分岐ノードに対する合流点ノードを
引き出し、前記変数に対する記号値を有するシャドー記
号表を作成し、制御フローにしたがって各ノードを次々
に評価して前記シャドー記号表内の前記変数に記号値を
割り当て、前記条件付分岐ノードを評価し、前記条件付
分岐ノードに応答して前記データ依存性条件の各々の可
能な値にたいして重複したシャドー記号表を作成し、前
記データ依存性条件の各々の可能な値を仮定して、前記
重複したシャドー記号表内の各々の前記変数に記号値を
割り当て、前記合流点に達するまで前記条件付分岐化ス
テートメントの各分岐内に含まれるノードの評価を続
け、各前記合流点ノードで前記重複したシャドー記号表
をマージし、すべての条件付分岐の評価を完了して、前
記制御フローグラフの前記終了ノードに達し、前記アル
ゴリズムを示す条件式を与えるステップから成るアルゴ
リズムを記号評価する方法。

【００９６】（２）前記制御フローグラフ変換ステップ
は、前記終了ノードがサクセッサノードを有していない
場合、前記複数のノードの各々に対し、サクセッサノー
ドのリストを与えるステップを含む第１項記載の方法。

【００９７】（３）前記逆ドミネータを計算するステッ
プは、各ノード自体を含む前記制御フローグラフ内に前
記ノードのすべてを含むよう各ノードに対する逆ドミネ
ータ候補点の一組を初期化し、前記終了ノード自体のみ
を含むよう前記終了ノードに対する逆ドミネータ候補点
の組を改変し、その逆ドミネータ候補点の組とそのサク
セッサノードのすべての逆ドミネータ候補点の組との論
理積を演算し、ノード自体を追加し、その結果得られる
逆ドミネータ候補点の組を発生し、前記逆ドミネータ候
補点の組に変化が生じなくなるまで上記ステップを繰り
返すと共に各ノードに対する逆ドミネータの組を発生す
ることから成る第２項記載の方法。

【００９８】（４）条件付分岐ノードに対する合流点ノ
ードを引き出すステップは、組内の他のすべての逆ドミ
ネータによりドミネートされている逆ドミネータを、ノ
ード自体を除く逆ドミネータの組から選択するステップ
を含む第３項記載の方法。

【００９９】（５）前記マージをするステップは、次の
３部構成条件式

【０１００】

【数１３】ｅ１？ ｅ２：ｅ３

【０１０１】（ここで、ｅ１は条件付分岐ノードのデー
タ依存性条件で、ｅ２は条件が真の場合の変数の値であ
り、ｅ３は条件が偽の場合の変数の値である）を使用
し、ｅ１をデータ依存性条件に置換し、ｅ２を前記デー
タ依存性条件に対し偽条件となる前記重複シャドー記号
表内の変数に割り当てられた記号値に置換し、ｅ３を前
記データ依存性条件に対し偽条件となる前記重複シャド
ー記号表内の変数に割り当てられた記号値に置換するこ
とから成る第１項記載の方法。

【０１０２】（６）前記マージするステップは、前記重
複したシャドー記号表内の前期変数の値を組み合わせ、
前記データ依存性条件の各々の可能な値に対し変数が前
記値となる時を特定することから成る第１項記載の方
法。

【０１０３】（７）データ依存性条件の値に応じて変数
に異なる値を割り当てる少なくとも２との分岐に至る少
なくとも一つの条件付分岐化ステートメントを有するア
ルゴリズムをトランスレートする装置であって、複数の
ノード（このノードの一つは前記条件付分岐ノードを示
す）を有する制御フローグラフに前記アルゴリズムを変
換するための手段と、前記複数のノードの各々に対し逆
ドミネータの組を計算するための手段と、前記条件付分
岐化ステートメントの前記分岐が収束する合流点ノード
を前記計算された逆ドミネータに応答して引き出すため
の手段と、前記条件式および前記変数を有するシャドー
記号表を作成するための手段と、前記制御フローグラフ
内の各ノードを次々に記号評価するための手段と、前記
条件付分岐化ノードを評価すると共に前記データ依存性
条件の各々の可能な値を取ることにより前記条件付分岐
ノードの評価に応答して前記条件付分岐ノードの各分岐
に対する前記シャドー記号表の一つの例を作成するため
の手段と、前記合流点ノードに達するまで前記条件付分
岐化ステートメントの各分岐の評価に応答して前記シャ
ドー記号表の前記それぞれの例内の前記変数に記号値を
割り当てるための手段と、前記合流点ノードに達した時
に前記シャドー記号表の前記例をマージするための手段
と、すべての条件付分岐の評価を続け、前記制御フロー
グラフの前記終了ノードに達するための手段と、前記ア
ルゴリズムを表す条件式を与えるための手段とから成る
アルゴリズムをトランスレートするための装置。

【０１０４】（８）前記制御フローグラフを変換するた
めの前記手段は、前記複数のノードの各々に対するサク
セッサノードおよびサクセッサノードを有しない終了ノ
ードのリストを与えるための手段を含む第７項記載の装
置。

【０１０５】（９）前記逆ドミネータ計算手段は、各ノ
ード自体を含む、前記制御フローグラフ内の前記ノード
のすべてを含むよう各ノードに対する逆ドミネータ候補
点の組を初期化する手段と、ノード自体を含むようサク
セッサノードを有しない前記終了ノードに対する逆ドミ
ネータ候補点の組を改変するための手段と、ノードごと
にその逆ドミネータの組とそのサクセッサノードのすべ
ての逆ドミネータの組との論理積を演算し、前記ドミネ
ータ候補点の組の変化が生じなくなるまで演算の結果得
られる逆ドミネータの組を発生し、ノードごとに逆ドミ
ネータの組を発生するための手段とから成る第８項記載
の装置。

【０１０６】（１０）合流点ノードを引き出すための手
段は、他のすべての逆ドミネータ候補点を逆ドミネート
している逆ドミネータを各ノードに対する逆ドミネータ
候補点の前記組から選択するための手段を含む、第９項
記載の装置。

【０１０７】（１１）前記マージする手段は、次の３部
構成条件式

【０１０８】

【数１４】ｅ１？ｅ２：ｅ３

【０１０９】（ここで、ｅ１は条件付分岐ノードのデー
タ依存性条件で、ｅ２は条件が真の場合の変数の値であ
り、ｅ３は条件が偽の場合の変数の値である）を使用
し、ｅ１をデータ依存性条件に置換し、ｅ２を前記デー
タ依存性条件に対し偽条件となる前記重複シャドー記号
表内の変数に割り当てられた記号値に置換し、ｅ３を前
記データ依存性条件に対し偽条件となる前記重複シャド
ー記号表内の変数に割り当てられた記号値に置換する第
７項記載の装置。

【０１１０】（１２）前記マージする手段は、前記重複
したシャドー記号表内の前記変数の値を組み合わせ、前
記データ依存性条件の各々の可能な値に対し変数が前記
値となる時を特定するステップを含む第１１項記載の装
置。

【０１１１】（１３）アルゴリズムを記号評価する方法
が提供される。このアルゴリズムは、少なくとも一つの
入力データの値に依存した少なくとも一つの条件付分岐
ステートメントを有する。この方法は、アルゴリズムを
複数のノード（各ノードは複数のステートメントのうち
の少なくとも一つを表す）を有する制御フローグラフに
変換する工程を含む。この制御フローグラフは、データ
依存性条件付分岐ステートメントの各々に対し一つの条
件付分岐ノードを更に含む。次に複数のノードの各々に
対する逆ドミネータを計算し、これら逆ドミネータから
各々の条件付分岐ノードに対する合流点ノードを引き出
す。本方法は、更にアルゴリズムで参照されるすべての
変数を収容するシャドー記号テーブルを作成し、かつ条
件付分岐ノードに応答してデータの各々の可能な値に対
し重複したシャドー記号テーブルを作成するようになっ
ている。本方法は更に制御フローにしたがって各ノード
を次々に記号的に評価し、シャドー記号テーブル内の変
数の各々に一つの記号値を割り当てる。各々の分岐に対
し、データを各々の可能な値とし、シャドー記号表内の
変数の各々に記号値を割り当てることにより条件付分岐
ノードを評価する。各々の分岐内のノードは、その合流
点ノードに達するまで評価される。次に重複されたシャ
ドー記号表がマージされる。すべての条件付分岐が評価
され、制御フローグラフの終了点に達するまで記号評価
を続け、アルゴリズムを表す条件式を得る。

【図面の簡単な説明】

【図１】ソフトウェアでの実現をハードウェア回路の実
現にトランスレートするための方法を示す大幅に簡略化
した図。

【図２】本発明の好ましい実施例の簡略化したフローチ
ャート。

【図３】本発明を良好に理解するための図例となるアル
ゴリズムの代表的制御フローグラフ。

【図４】ループ構造を有するアルゴリズムの代表的制御
フローグラフ。

【図５】反復回数が入力データに依存するループ構造を
有するアルゴリズム代表的制御フローグラフ。

【符号の説明】 １ ソフトウエア実現ロード ３ データフローグラフ ３６ 条件付ノード ４３，４６，４７ ノード ５１，５２，５４ 条件付分岐ノード ５６ 分岐点ノード ｃ，ｂ，ｉ，ｙ，ｘ 変数

Claims (2)

【特許請求の範囲】
1. 【請求項１】複数の変数の値を操作する複数のステート
   メントを有し、更にデータ依存条件の値に依存する少な
   くとも一つの条件付分岐化ステートメントを有するアル
   ゴリズムを記号評価する方法であって、 開始ノードおよび終了ノードを含み複数のノード（各ノ
   ードは前記複数のステートメントのうちの少なくとも一
   つを示す）を有し、前記データ依存性条件付分岐化ステ
   ートメント用の条件付分岐ノードを含む制御フローグラ
   フに前記アルゴリズムを変換し、 前記複数のノードの各々に対する逆ドミネータの組を計
   算し、 前記逆ドミネータに応答して各々の条件付分岐ノードに
   対する合流点ノードを引き出し、 前記変数に対する記号値を有するシャドー記号表を作成
   し、 制御フローに従って各ノードを次々に評価して前記シャ
   ドー記号表内の前記変数に記号値を割り当て、 前記条件付分岐ノードを評価し、前記条件付分岐ノード
   に応答して前記データ依存性条件の各々の可能な値に対
   して重複したシャドー記号表を作成し、前記データ依存
   性条件の各々の可能な値を仮定して、前記重複したシャ
   ドー記号表内の各々の前記変数に記号値を割り当て、 前記合流点に達するまで前記条件付分岐化ステートメン
   トの各分岐内に含まれるノードの評価を続け、 各前記合流点ノードで前記重複したシャドー記号表をマ
   ージし、 すべての条件付分岐の評価を完了して、前記制御フロー
   グラフの前記終了ノードに達し、 前記アルゴリズムを示す条件式を与えるステップから成
   るアルゴリズムを記号評価する方法。
2. 【請求項２】データ依存性条件の値に応じて変数に異な
   る値を割り当てる少なくとも２との分岐に至る少なくと
   も一つの条件付分岐化ステートメントを有するアルゴリ
   ズムをトランスレートする装置であって、 複数のノード（このノードの一つは前記条件付分岐ノー
   ドを示す）を有する制御フローグラフに前記アルゴリズ
   ムを変換するための手段と、 前記複数のノードの各々に対し逆ドミネータの組を計算
   するための手段と、 前記条件付分岐化ステートメントの前記分岐が収束する
   合流点ノードを前記計算された逆ドミネータに応答して
   引き出すための手段と、 前記条件式および前記変数を有するシャドー記号表を作
   成するための手段と、 前記制御フローグラフ内の各ノードを次々に記号評価す
   るための手段と、 前記条件付分岐化ノードを評価すると共に前記データ依
   存性条件の各々の可能な値を取ることにより前記条件付
   分岐ノードの評価に応答して前記条件付分岐ノードの各
   分岐に対する前記シャドー記号表の一つの例を作成する
   ための手段と、 前記合流点ノードに達するまで前記条件付分岐化ステー
   トメントの各分岐の評価に応答して前記シャドー記号表
   の前記それぞれの例内の前記変数に記号値を割り当てる
   ための手段と、 前記合流点ノードに達した時に前記シャドー記号表の前
   記例をマージするための手段と、 すべての条件付分岐の評価を続け、前記制御フローグラ
   フの前記終了ノードに達するための手段と、 前記アルゴリズムを表す条件式を与えるための手段とか
   ら成るアルゴリズムをトランスレートするための装置。