(57)【要約】  集積回路設計内のループを解析し、処理する方法および装置が示される。一実施形態によれば、処理は、ループの展開を含む。別の実施形態では、処理は、ループのパイプライン化を含む。別の実施形態では、処理は、ループのマージを含む。開示の実施形態の何れにおいても、各ループは、独立ループ、依存ループ、またはそれらの何らかの組み合わせを含む。ループを処理する他の実施形態、並びに、開示の方法の結果として生じる集積回路および回路設計データベースも、開示される。また、開示の方法を実行する命令を格納しているコンピュータ実行可能媒体も、開示される。【特許請求の範囲】
【請求項１】
ハードウェア回路を設計するために使用される動作合成ツールにおける方法であって、
第１のループを検出するステップであって、前記第１のループは、第１の項目を含む、ステップと、
第２のループを検出するステップであって、前記第２のループは、前記第１の項目に依存している第２の項目を含む、ステップと、
前記第１のループを、前記第２のループと少なくとも部分的にマージするステップと、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記第１のループは、第１の親ループ内に第１のサブループを含む、方法。
【請求項３】
請求項２に記載の方法であって、前記第２のループは、第２の親ループ内に第２のサブループを含む、方法。
【請求項４】
請求項２に記載の方法であって、前記第２のループは、前記第１の親ループ内に第２のサブループを含む、方法。
【請求項５】
請求項１に記載の方法であって、第２のループを検出する前記ステップは、前記第２のループに関する依存関係解析を実行するステップを含む、方法。
【請求項６】
請求項５に記載の方法であって、前記第２のループに関する依存関係解析を実行する前記ステップは、前記第２のループ内でアクセスされる配列における少なくとも１つの個別ビットをアドレス指定するステップを含む、方法。
【請求項７】
請求項１に記載の方法を実行するためのコンピュータ実行可能命令が格納されているコンピュータ可読媒体。
【請求項８】
請求項１に記載の方法を使った、複数の少なくとも部分的にマージされたループを含むハードウェア回路設計。
【請求項９】
ネットワークで接続されたコンピュータにおける方法であって、
複数の依存ループを受け取るステップと、
前記複数の依存ループを解析するステップと、
前記複数の依存ループをマージするステップと、
を含む方法。
【請求項１０】
方法であって、
ハードウェア回路のソース・コード表現内のループを識別するステップであって、第１のループは、第２のループに依存している、ステップと、
少なくとも前記第１のループと第２のループとをマージするステップと、
を含む方法。
【請求項１１】
集積回路を設計するシステムであって、
集積回路のソース・コード記述を受け取る入力装置と、
ソフトウェアを実行するプロセッサと、
前記ソース・コード内のループを識別するソフトウェアと、
少なくとも２つのループをマージするソフトウェアであって、前記ループの少なくとも１つは、依存ループを構成している、ソフトウェアと、
出力装置と、
を備えるシステム。
【請求項１２】
方法であって、
入力コードを受け取るステップであって、前記入力コードは、複数のループに関連するコードを含み、前記複数のループの少なくとも１つは、依存ループを構成している、ステップと、
前記入力コードを処理するステップであって、前記複数のループの少なくとも２つをマージするステップを含むステップと、
出力コードを提供するステップであって、前記出力コードは、前記少なくとも２つのマージされたループを含む、ステップと、
を含む方法。
【請求項１３】
請求項１２に記載の方法であって、前記入力コードは、Ｃ＋＋コードを含む、方法。
【請求項１４】
請求項１２に記載の方法であって、前記出力コードは、レジスタ転送レベル（ＲＴＬ）コードを含む、方法。
【請求項１５】
動作合成ツール用ユーザ・インターフェースにおける方法であって、
複数のループに対応するマージ可能ディレクティブを設定する複数の選択肢を受け取るステップであって、前記複数のループの少なくとも１つは、依存ループを構成している、ステップと、
前記複数の選択肢の１つを選択するステップと、
を含む方法。
【請求項１６】
請求項１５に記載の方法であって、前記複数の選択肢は、真と偽とを含む、方法。
【請求項１７】
請求項１５に記載の方法であって、
デフォルト選択肢を受け取るステップであって、前記デフォルト選択肢は、ヒューリスティックス法に基づくものである、ステップを、
更に含む方法。
【請求項１８】
ハードウェア回路を設計する際の方法であって、
ハードウェア設計のソース・コード表現内のループを識別するステップと、
グラフィカル・ユーザ・インターフェース（ＧＵＩ）を介して、複数の前記ループをマージすることを示す指示を受け取るステップであって、前記複数のループの少なくとも１つは、依存ループを構成している、ステップと、
前記複数のループをマージするステップと、
を含む方法。
【請求項１９】
請求項１８に記載の方法であって、
前記識別されたループをマージしないことを示す指示を後で受け取るステップを、
更に含む方法。
【請求項２０】
ハードウェア回路設計を作成する方法であって、
複数のループの可能なマージに関連する選択肢を選択するステップであって、前記複数のループは、少なくとも１つの依存ループを含む、ステップと、
前記選択された選択肢が前記ハードウェア回路設計に及ぼし得る少なくとも１つの影響に関する情報を受け取るステップと、
を含む方法。
【請求項２１】
請求項２０に記載の方法であって、前記複数のループの１つは、前記複数のループの別の１つとすでにマージされている、方法。
【請求項２２】
集積回路を設計する方法であって、
ハードウェア設計のソース・コード表現内のループを識別するステップと、
グラフィカル・ユーザ・インターフェース（ＧＵＩ）を介して、複数の前記ループの潜在的なマージを解析するよう求める要求を受け取るステップであって、前記複数のループは、少なくとも１つの第２のループに依存している第１のループを含む、ステップと、
前記複数のループの前記潜在的なマージの解析を提供するステップと、
を含む方法。
【請求項２３】
集積回路を設計する方法であって、
第１のループを少なくとも部分的に展開するステップであって、前記第１のループは、依存ループを構成している、ステップと、
前記第１のループを第２のループとマージするステップと、
を含む方法。
【請求項２４】
集積回路を設計する方法であって、
第１のループを第２のループとマージするステップであって、前記第２のループは、依存ループを構成している、ステップと、
前記第１のループと前記第２のループとをパイプライン化するステップと、
を含む方法。
【請求項２５】
方法であって、
第１のループを識別するステップと、
第２のループを識別するステップであって、前記第１のループは、前記第２のループに依存しており、前記第２のループは、前記第１のループとマージ可能である、ステップと、
前記第１のループと前記第２のループとを、一緒に、第１のマージされたループにマージするステップと、
を含む方法。
【請求項２６】
請求項２５に記載の方法であって、
第３のループを識別するステップであって、前記第３のループは、前記第１のループおよび前記第２のループとマージ可能である、ステップと、
前記第１のマージされたループと前記第３のループとを、一緒にマージするステップと、
を更に含む方法。
【請求項２７】
請求項２５に記載の方法であって、
ループ・マージ順序を確立するステップと、
前記ループ・マージ順序に従って、前記第１のループと、第２のループと、第３のループとをマージするステップと、
を更に含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、その両方が、参照により本明細書に組み込まれている、２００４年５月２８日に出願した、「ＤＰＥＮＤＥＮＴ  ＬＯＯＰ  ＭＥＲＧＩＮＧ  ＩＮ  Ａ  ＢＥＨＡＶＩＯＲＡＬ  ＳＹＮＴＨＥＳＩＳ  ＴＯＯＬ」という名称の米国特許仮出願第６０／５７５，２１０号、および２００４年１１月１０日に出願した、「ＬＯＯＰ  ＭＡＮＩＰＵＬＡＴＩＯＮ  ＩＮ  Ａ  ＢＥＨＡＶＩＯＲＡＬ  ＳＹＮＴＨＥＳＩＳ  ＴＯＯＬ」という名称の米国特許出願第１０／９８５，３９８号の利益を主張するものである。
【０００２】
（技術分野）
本出願は、一般に、集積回路（例えばフィールド・プログラマブル・ゲート・アレイなど）を作成する動作合成ツールに関し、より詳細には、設計内のループの解析および処理に関する。
【背景技術】
【０００３】
電子設計自動化（ＥＤＡ）の出現で、複雑なハードウェア・システムの設計は、もはや、ハードウェア回路図から始まるものではなくなった。その代わりとして、回路設計は、通常、ハードウェア・システムの動作または機能を記述するソフトウェア・プログラムから始まる。１つの手法例では、電子回路設計の動作または機能は、ハードウェア記述言語（ＨＤＬ）（例えば、ＶＨＤＬ、Ｖｅｒｉｌｏｇ、他の同様の言語など）を使って記述されてもよい。回路設計者は、制約条件（例えば、クロック期間、データ・パス要素の数および種類、所望のクロック・サイクル数など）を変更することによって、動作合成ツールに、代替のアーキテクチャを生成するよう指図する。動作合成ツールは、ＨＤＬプログラムをレジスタ転送レベル（ＲＴＬ）記述に変換する。ＲＴＬ記述は、最終的に、回路内の構成部品のリストと構成部品間の相互接続とを含むネットリストを生成するのに使用される。このネットリストが、実際の集積回路を作成するのに使用される。
【０００４】
以下の表１に示すＨＤＬソース・コードの一例では、配列である３つの変数（ａ、ｂ、ｃ）を宣言している。各配列は、１０２４の８ビット・ワードを含む。コードは、まず、配列内の各要素の型を定義する「ｓｕｂｔｙｐｅ」を宣言する。次いで、コードは、配列自体を表す「ｔｙｐｅ」を定義する。最後に、それぞれが１つの配列を表す各変数が宣言される。
【０００５】
【表１】
2008501185.tif 000002
【０００６】
一般に、各変数には、以下の表２に示すループなどのループを使ってアクセスされ得る。配列がメモリにマップされるときには、配列内の各要素が１つのメモリ位置にマップされる。例えば、ａ（０）はアドレス０にマップし、ａ（１）はアドレス１にマップし、ａ（１０２３）はアドレス１０２３にマップする。
【０００７】
【表２】
2008501185.tif 000003
【０００８】
設計者は、ＨＤＬソース・コードを完成させた後、そのソース・コードを合成ツールによって実行してもよい。典型的な合成ツールは、設計者が、回路の性能を解析するのに使用することのできるレポートを生成する。例えば、ユーザは、回路の面積および待ち時間を検査して、回路ループ構成が許容可能であるかどうか判定することができる。ループ構成が許容可能でない場合、設計者は、通常、エディタに戻り、ループを展開し、またはパイプライン化するようにソース・コードを再編集し、合成ツールによってそのソース・コードを再度実行する。かかる設計変更の技法は、時間がかかり、効率が悪い。しかも、設計者は、ソース・コードを変更する間、ループ構成が設計をどのように変更するか容易に視覚化することができない。
【０００９】
ＲＴＬの方法は、これまで、単純なハードウェア・ブロックをシミュレートし、設計するには十分であったが、今日では、様々な点で十分というにはほど遠いものとなっている。新しいディジタル信号処理（ＤＳＰ）用途の設計の複雑度は、従来のＲＴＬの方法をしのぐものとなっている。そのため、設計者は、自らのアルゴリズムを迅速に検証するために、Ｃ＋＋やＭａｔｌａｂ（登録商標）に移行している。このより高度な抽象化は、システム検証には役立っているが、同時に、高水準言語を使用するシステム設計者とＲＴＬをハンドコードするハードウェア設計者の間の技術ギャップを広げるものともなっている。
【００１０】
設計は、シングルブロックまたはマルチブロックの機能ユニットから、組み込み式コアと、専用の計算集約的アルゴリズムを実施する複雑なハードウェアを含む大規模システムへと進化している。これらの前進にもかかわらず、技術者は、依然として、マイクロアーキテクチャ定義、手書きのＲＴＬ、ＲＴＬ合成による面積／速度最適化などといった、手作業によるステップを伴う反復的なＲＴＬの方法を使用する。このプロセスは、時間がかかり、誤りを犯しやすい。しかも、マイクロアーキテクチャも、目的技術特性も、共に、ＲＴＬ記述へとハードコードされるため、ＲＴＬの再利用または目標変更という考え方全体が、実際の用途には実用的でないものになっている。
【発明の開示】
【課題を解決するための手段】
【００１１】
（発明の概要）
ある設計をどのようにしてハードウェアに統合するかを完全に制御すること、または制御を改善することが求められており、それによって幾つかの利点がもたらされるはずである。例えば、設計内のすべてのポートと、配列と、ループとの図式的表示を提示するアーキテクチャ制約条件ツールは、様々なハイレベル制約条件の何れかが適用されることを可能にするはずである。例えば、これらの制約条件には、ループ展開や、パイプライン化や、マージなどが含まれ得るであろう。かかるツールは、ハードウェア実装形態の正確な制御を実現し、ずっと短時間での、著しく高品質な設計への対話型収束を可能にするはずである。
【００１２】
ループ展開、パイプライン化、およびマージの、様々な、新規で、非自明な方法の例を、関連する装置と共に開示する。これらの方法は、例えば、特定用途向け集積回路（ＡＳＩＣ）や、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）や、他の同様のプログラマブル論理デバイスの設計を実装するのに使用され得る。
【００１３】
開示の実施形態の１つは、動作合成ツールにおいてハードウェア回路を設計する方法の一例である。この方法は、ループを見つけ出し、それらの一部または全部を一緒にマージするステップを伴う。この方法によれば、第１のループが検出される。第１のループは、項目（変数にアクセスするステートメントなど）を含む。また、第２のループも検出される。第２のループも、やはり、項目（変数にアクセスするステートメントなど）を含む。幾つかの実施形態では、第２のループ内の変数が、第１のループ内の変数に依存している。別の実施形態では、第２のループまたは第１のループ内の幾つかの変数が、２つのループのどちらかの他の変数に依存していていることもある。この方法によれば、２つのループは、互いに、部分的に、または完全にマージされる。別の実施形態では、各ループは、他のループとマージされる。
【００１４】
開示の実施形態の別のものは、集積回路（ＦＰＧＡなど）を設計する方法の一例である。この方法によれば、ハードウェア回路のソース・コード表現が解析され、その表現内のループが識別される。一実施形態では、第１のループが第２のループに依存している。別の実施形態では、任意の数のループが他のループに依存していてもよい。その場合、少なくとも２つのループが、一緒にマージされる。
【００１５】
別の開示の実施形態は、動作合成ツールのユーザ・インターフェース内の方法の一例である。この方法によれば、マージ可能ディレクティブを設定する幾つかの選択肢がユーザ（設計者など）に提供される。選択肢の１つが選択され、それによって、マージ可能ディレクティブが設定される。一実施形態では、一緒にマージされ得るループをマージするために、真のマージ可能ディレクティブが設けられる。別の実施形態では、デフォルトの選択肢が、ヒューリスティック（真など）に基づいて提供されてもよい。
【００１６】
開示の実施形態の何れも、コンピュータ可読媒体に格納されているコンピュータ実行可能命令を用いてプログラムされたコンピュータによって実行されてもよい。これらの実施形態において、コンピュータ実行可能命令は、コンピュータに、開示の実施形態の何れかを実行させる。更に、開示の実施形態の何れかを使って、コンピュータ可読媒体に格納されている回路設計情報を更新し、または変更することも可能である。従って、本明細書に示す方法によって同期された回路設計を格納している改変された設計データベースも開示する。かかる方法は、例えば、独立型ワークステーション上や、ネットワークを介して実行され得る。
【００１７】
なお、上記その他の特徴を、以下で、添付の図面を参照して述べる。
【発明を実施するための最良の形態】
【００１８】
以下で開示するのは、回路設計内のループを解析し、処理する方法の代表的な実施形態である。開示の方法は、如何なる点においても限定的なものと解釈されるべきではない。そうではなく、本開示は、様々な開示の実施形態の、単独での、また、実施形態相互の様々な組み合わせおよび部分的組み合わせとしての、新規で、非自明な特徴および態様を対象とするものである。これらの方法は、そのどんな特定の態様にも、特徴にも、組み合わせにも限定されるものではなく、開示する方法は、どんな１つまたは複数の特定の利点が存在することも、問題が解決されることも必要とするものではない。
【００１９】
開示する方法の幾つかの動作は、提示に好都合なように、特定の順番で記述されるが、このような記述は、以下に示す特定の言語によって特定の順序付けが必要とされるのでない限り、再配置を包含するものであることを理解すべきである。例えば、順次に記述される動作は、場合によっては、再配置されても、同時に実行されてもよい。更に、簡単にするために、添付の図は、開示する方法が、他の方法と併せて使用され得る様々なやり方を示さないこともある。加えて、説明では、「判定する」や「評価する」などの用語を使っ
て開示する方法を記述することもある。これらの用語は、実行される実際の操作の高度な抽象化である。これらの用語に対応する実際の動作は、個々の実装に応じて異なり、当分野の技術者により容易に認識され得るものである。
【００２０】
開示の実施形態は、多種多様な集積回路に適用され得る。順次集積回路（または順次回路）とは、その出力が、その現在の入力だけでなく、おそらくは、時間的に随意にはるか以前の、過去の入力シーケンスにも依存する回路である。順次回路の例には、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、システム・オン・チップ（ＳｏＣ）などのプログラマブル論理デバイス（ＰＬＤ）が含まれる。順次回路は、フリップ・フロップや、同期ＲＡＭ素子や、ラッチなど、少なくとも１つの順次回路素子を含む。順次回路素子（または順次素子）とは、一般に、その出力状態変化が、自走クロック信号によって指定される時刻に発生する任意の回路素子を指す。
【００２１】
開示の方法の何れも、コンピュータ可読媒体上に格納され、コンピュータ上で実行されるソフトウェアを使って実行され得る。かかるソフトウェアは、例えば、論理合成や物理合成などに使用される電子設計自動化（ＥＤＡ）ソフトウェア・ツールを含むことができる。かかるソフトウェアは、単一のコンピュータ上でも、（例えば、インターネット、広域ネットワーク、ローカル・エリア・ネットワーク、クライアント／サーバ・ネットワーク、あるいは他の同様のネットワークなどを介して）ネットワークで接続されたコンピュータ上でも実行され得る。明確にするために、ソフトウェアに基づく実装形態の幾つかの選択された態様だけを記述する。当分野でよく知られているその他の詳細は省略する。例えば、開示の技術は、どんな特定のコンピュータ言語にも、プログラムにも、コンピュータにも限定されるものではないことを理解すべきである。同じ理由で、コンピュータ・ハードウェアについても詳細に記述しない。
【００２２】
（集積回路生成）
図１に、集積回路を生成するシステム１００を示す。設計者は、通常、別個のエディタ（不図示）を使ってソース・コード・ファイル１０２を生成することによって、集積回路の動作記述を作成する。ソース・コードは、ＨＤＬとして一般的に記述され、Ｃ、Ｃ＋＋、ＶＨＤＬ、Ｖｅｒｉｌｏｇ、または他の任意の適切な言語で書かれてもよい。また、ソース・コードは、ＳｙｓｔｅｍＣなど、Ｃ＋＋派生言語で書かれてもよい。ソース・コード１０２が完成すると、動作合成ツール１０４が、ソース・コード・ファイル１０２を読み込み、設計者が、設計プロセスの初期段階で回路アーキテクチャを評価し、変更することができるようにする。具体的には、ソース・コード１０２は、動作記述をデータ構造として保持する中間データベース１０６に読み込まれてもよい。このデータ構造は、合成中間フォーマット（ＳＩＦ）と呼ばれ、グラフィカル・ユーザ・インターフェース（ＧＵＩ）１０８をなど用いてユーザによる変更が可能である。動作合成ツールは、ソース・コード内のループを識別することができる。一実施形態では、ＧＵＩは、設計者が、実行時間が最大である識別されたループを展開し、かつ／またはパイプライン化することもできるようにする。ループを処理する（例えば、マージしたり、パイプライン化したりする）ことによって、回路設計は、最適化され得る。加えて、設計者は、異なるパイプライン化と、展開と、マージとの組み合わせに関連付けられる面積および待ち時間を迅速に評価することもできる。設計者がアーキテクチャに満足すると、１２０に示すようにＲＴＬコードが生成される。次いで、ＲＴＬコードに対してさらなる処理が実行されて、最終的に、集積回路が生成される。動作合成ツール１０４は、ＧＵＩを表示する任意の表示装置またはモニタを備え、マウスや、キーボードや、他の任意の入力装置など、任意の所望のユーザ入力を備える任意の所望の汎用コンピュータ上で実行されてもよい。
【００２３】
図２に、ハードウェア設計ツールに従って集積回路を生成する流れ図２００を示す。ソース・コードが、設計ツールにロードされる２０２。設計ツールは、ソース・コード内の
ループを識別する２０４。次いで、設計ツールは、ループの処理を可能にする２０６。設計者が満足すると、最終的な回路設計が出力される２０８。
【００２４】
図３に、集積回路を生成するより詳細な流れ図の例３００を示す。プロセス・ブロック３０２で、設計者が、すでに説明したようにソース・コードを作成する。図１の動作合成ツール１０４が、ソース・コード３０４を図１の中間データベース１６に読み込み、設計者による変更が可能なデータ構造を生成する。データ構造を生成するときに、合成ツールは、ソース・コードの解析を行う。例えば、合成ツールは、ソース・コード内の演算子、信号、および変数をサーチし、これらのＨＤＬステートメントに基づいてデータ構造を生成する。加えて、合成ツールは、ディレクティブをサーチし、それらのディレクティブおよび／または１組のデフォルト選択を使って、データ構造内のハードウェア記述を設定する。データ構造は、ループを様々な形で表すことのできるデータ・モデルであり、最も一般的なものが、最初に動作合成ツールに読み込まれるときなどのソース・コードのマッピングである。
【００２５】
３０６で、設計内の任意のループ識別が行われ、識別されたループの何れかがマージ可能であるかどうかが判定される。２つ以上のループがマージ可能であると判定された場合、設計者に、それらのマージ可能なループを展開し、マージし、またはパイプライン化する機会が与えられる３０８。ループ・マージには、それだけに限らないが、あるループのループ本体を別のループのループ本体に挿入し、それによって、より高速であり、またはさらなる最適化の可能性を明示し得る単一のループを形成することを伴ってもよい。次いで、回路設計が最終決定されてもよい３１０。プロセスの別のステップには、ＲＴＬコードの生成３１２と、ＲＴＬコードのシミュレート３１４と、ＲＴＬ合成の実行３１６と、結果として生じるゲート・レベルの設計の検証／解析３１８とが含まれていてもよい。
【００２６】
（プログラミング言語の例）
本明細書で開示する例は、一般に、Ｃ言語で書かれたコードを伴う実施形態を記述するものである。しかしながら、これらの例は、説明のためのものにすぎず、開示の技術の範囲を限定するものと解釈されるべきでないことは明白なはずである。例えば、開示の技術は、幅広いプログラミング言語およびデータ構造の何れを使っても実施され得る。
【００２７】
（ループ反復カウンタ）
ループ反復カウンタは、一般に、あるループの本体が、そのループの開始以来実行された回数を表す。ループが終了する前に反復する回数は、定数とすることもでき、データ依存とすることもできる。反復数が定数であるかどうかを問わず、最大ループ反復数と呼ばれる、統計的に決定できる最大数があってもよい。一般に、ループ反復カウンタは、ループの最初の反復をゼロとして開始する。以下の表３に示すループ例の各反復において、ループの各反復の開始時の変数ｘは、１００から２を差し引いてループ反復カウンタを乗じたものに等しい。
【００２８】
【表３】
2008501185.tif 000004
【００２９】
（ループ・マージ）
ループ・マージは、通常は順次に実行されるはずのループの並列実行を可能にすること
によって、ある設計内の待ち時間および面積消費を低減するのに使用され得る技法である。一般に、ループ・マージは、マージされるループ内のステートメントの並べ換えを伴う。一実施形態では、ループ・マージは、それぞれが順次に実行される２つの別個のループの、単一の、等価なループとの置き換えである。この実施形態では、マージされるループが２つの別個のループと同じ１つまたは複数の機能を実行するように、マージされるループの本体が、単一のループの各本体から構築される。ツールは、動作の順序が大域的に変更されてもよく、また、マージされたループが、実行されるときに、マージ前の別個のループのそれぞれのステートメントを、正しい条件の下で、正しい回数実行するよう保証することを必要とし得る。
【００３０】
【表４】
2008501185.tif 000005
【００３１】
一例では、３つのマージ可能なループが一緒にマージされる。３つのループ例を上記表４に示す。
【００３２】
【表５】
2008501185.tif 000006
【００３３】
表４に示すループ例を使うと、最初のステップは、Ｌｏｏｐ１をＬｏｏｐ２とマージすることを含み、結果として、上記表５に示す新しいループ１を生じてもよい。
【００３４】
【表６】
2008501185.tif 000007
【００３５】
２つのループがマージされた後で、マージされたループを別のループとマージすることも可能である。この例では、今や、Ｌｏｏｐ１とＬｏｏｐ２とが一緒にマージされており、結果として生じたループ構造は、Ｌｏｏｐ３とマージされて、上記表６に示す新しいＬｏｏｐ１を生じてもよい。
【００３６】
上記各ステップは、表６に示すループ構造で繰り返されてもよい。例えば、ループの最初の階層がマージされてから、ｓｕｂｌｏｏｐ１ループとｓｕｂｌｏｏｐ２ループは、両方ともマージ可能な場合には、マージされ得るはずである。
【００３７】
ループ・マージは、しばしば、様々なループ（例えば、ｆｏｒループ、ｗｈｉｌｅループ、ｕｎｔｉｌループなど）と、任意の数の追加のループ制御（例えば、ｃｏｎｔｉｎｕ
ｅステートメントやｂｒｅａｋステートメントなど）との組み合わせを扱う必要のある複雑な変換を伴う。これらの構文の多くが、しばしば、プログラムの明確さおよび読みやすさのために使用され、プログラマの便宜のためにも使用されるが、その同じ機能が、それらの構文なしで表現され得ることもある。例えば、多くのＣ言語マニュアルは、同等なｗｈｉｌｅループを示すことによってｆｏｒループの動作を定義している。
【００３８】
（ループ依存関係）
あるループ内の複数のステートメントが独立している場合、それらは、普通、再配列され得る（例えば、交換されるなど）。データ依存関係は、一般に、第１のステートメントが、後で、第２のステートメントにおいて使用される変数に値を代入するときに発生する。逆依存関係は、普通、第２のステートメントが、第１のステートメントで使用される変数に値を代入するときに発生するという。
【００３９】
【表７】
2008501185.tif 000008
【００４０】
【表８】
2008501185.tif 000009
【００４１】
上記表７に示す２つのステートメントは独立である。というのは、どちらのステートメントも、他方のステートメントによって使用されるどんな変数にも値を代入しないからである。よって、２つのステートメントは、（例えば、上記表８に示すように）再配列され得る。
【００４２】
【表９】
2008501185.tif 000010
【００４３】
上記表９に示す２つのステートメントは、データ依存である。というのは、変数ｘが、第１のステートメントに書かれており、第２のステートメントで読み取られているからである。これは、第１のステートメントにおける乗算の結果が、第２のステートメントにおける加算の引数として使用されることを意味している。よって、乗算は、加算に対してデータ依存関係を有するということができ、従って、加算の前に実行されなければならない。
【００４４】
【表１０】
2008501185.tif 000011
【００４５】
【表１１】
2008501185.tif 000012
【００４６】
【表１２】
2008501185.tif 000013
【００４７】
一例では、（上記表１０に示す）２つのステートメントが、それらが直接には交換され得ないことを意味する、逆依存関係を示している。データ依存関係がないため、依存関係は、代入間のものであり、乗算と加算の間のものではない。この依存関係を解決する１つの方法が、上記表１１に示すように、一時変数ｙ＿ｔｍｐを加えて、ｙへの代入から加算を分離することである。これで、ｘとｙ＿ｔｍｐへの代入は、独立となり、従って、これらのステートメントは、上記表１２に示すように、交換され得る。
【００４８】
（ループ依存関係解析）
複数のループが存在する幾つかの実施形態では、任意のマージが行われる前に、独立ループ・データフロー依存関係解析を実行する必要があることもある。独立ループ・データフロー依存関係解析では、ループによって書かれているあらゆる変数が、設計内の各ループごとに識別されてもよい。変数は、そのループ内部で、または任意のサブループ内でその変数への代入がある場合に、書き込まれていると考えられる。同じループ階層内のループの対ごとに、第１のループ内に書き込まれている変数が、第２のループにおいて読み取られ、または書き込まれているかどうかがチェックされる。
【００４９】
状況によっては、ループ依存関係解析は、単一ステートメントだけに適用されてもよい。状況によっては、かかる解析は、ステートメントのブロックに適用されてもよい。解析の間に行われ得る幾つかの決定には、ステートメントがループを越えて移動され得るかどうか、および２つ以上の完全なループが再配列され得るかどうかが含まれていてもよい。
【００５０】
一例では、上記表４に示す３つのループ例を使って、Ｌｏｏｐ１が、変数「ａ」と「ｂ」と「ｊ」とに書き込み、変数「ａ」と「ｃ」と「ｊ」とを読み取る。また、Ｌｏｏｐ１は、ｓｕｂｌｏｏｐ１ループで読み取られ、書き込まれる任意の変数を読み取り、書き込むものであるとも考えられる。Ｌｏｏｐ２は、「ｋ」と「ｘ」とを書き込み、「ｋ」と「ｃ」とを読み取り、ｓｕｂｌｏｏｐ２内の変数すべての読取り／書込みを行う。Ｌｏｏｐ３は、「ｋ」と「ｏｕｔ」とを書き込み、「ｋ」と「ｂ」とを読み取る。
【００５１】
この例では、独立ループ・データフロー依存関係解析が、以下の結果をもたらす。即ち、Ｌｏｏｐ１とＬｏｏｐ２とＬｏｏｐ３とは、ｓｕｂｌｏｏｐ１とｓｕｂｌｏｏｐ２とに対する依存関係を持たない。というのは、これらが、異なるループ・ネスティング・レベルにあるからである。サブループ内に依存関係がないものと仮定すると、Ｌｏｏｐ１は、Ｌｏｏｐ２への依存関係を持たない。サブループ内に依存関係がないものと仮定すると、Ｌｏｏｐ２は、Ｌｏｏｐ３への依存関係を持たない。しかしながら、Ｌｏｏｐ１とＬｏｏｐ３の間には依存関係がある。その依存関係は、Ｌｏｏｐ１で書き込まれ、Ｌｏｏｐ３で読み取られる変数ｂである。ｋは、Ｌｏｏｐ３の開始時に無条件で書き込まれるため、Ｌｏｏｐ２とＬｏｏｐ３において同じ変数であるとは考えられないことに留意すべきである。ｋの依存関係は、無条件代入の後に、ｋの別個の変数を作成することによって解決されてもよい。
【００５２】
他の例では、依存配列アクセス解析が行われてもよい。かかる解析では、あるループの内部で読み取られ、または書き込まれ、定数およびループ反復子を含む式を使ってのみ索引付けされる各配列ごとに、配列への索引が、ループ反復だけに基づく式として計算され
てもよい。上記表４に示すループの例では、Ｌｏｏｐ１内の「ｂ」へのアクセスは、ループ反復カウンタに等しい。Ｌｏｏｐ３内の「ｂ」へのアクセスは、ループ反復カウンタから１を差し引いたものに等しい。従って、Ｌｏｏｐ１とＬｏｏｐ３の間の依存関係は、本質的に、Ｌｏｏｐ１が、Ｌｏｏｐ２の前に１反復を開始する必要があるというものである。
【００５３】
（部分的ループ依存関係の抽出）
ループは、一般に、各ループ間にデータ依存関係がある場合には、独立ループ・マージ技法を使ってマージされ得ない。
【００５４】
【表１３】
2008501185.tif 000014
【００５５】
【表１４】
2008501185.tif 000015
【００５６】
一例として、２つのループ（Ｌｏｏｐ１とＬｏｏｐ２）が、上記表１３に示されている。この例で、Ｌｏｏｐ１は、値を計算し、それらを配列ｔｍｐに格納する。次いで、Ｌｏｏｐ２でこれらの値を使って、さらなる計算が行われる。従って、Ｌｏｏｐ１は、Ｌｏｏｐ２の前に実行されなければならず、これが、実現可能な並列性を低下させ、実行時間を増大させる。ループが変更されないままである場合、各反復は、上記表１４に示す順序で実行される。表１４において、ＢｏｄｙＮ．ｉは、ＬｏｏｐＮの反復数ｉを表す。
【００５７】
並列性を探るために、全体としての各ループ間ではなく、ループの単一反復間での依存関係を見つけ出そうとする解析が行われ得る。かかる依存関係を、部分的依存関係と呼んでもよい。この種の並列性は、各ループを展開することによって明示され得る。というのは、そうすれば、部分的依存関係が、通常の依存関係になるはずだからである。しかしながら、展開は、コード・サイズを増大させ、反復から規則性を取り除くこともあるため、状況によっては望ましくないこともある。
【００５８】
【表１５】
2008501185.tif 000016
【００５９】
この例では、配列ｔｍｐへのアクセスが規則的であり、単一の反復が考慮に入れられる場合には、上記表１５に示すように、各ループの反復間のデータ依存関係が、より正確に記述され得る。
【００６０】
【表１６】
2008501185.tif 000017
【００６１】
この例では、Ｌｏｏｐ２は、どんなデータ依存関係も侵害することなく、Ｌｏｏｐ１の何回かの反復が完了した後で開始することもできる。それら２つのループを単一ループにマージすることが可能であり、Ｂｏｄｙ２が２反復にわたって据え置かれる場合、マージされるループは、１３反復を有し、上記表１６に示す順序で実行されるはずである。ここで、Ｂｏｄｙ１．ｉｃは、Ｂｏｄｙ２．（ｉｃ−２）で最初に使用されるｔｍｐ［ｉ］を計算し、ｉｃは、それぞれのループの反復カウンタである。
【００６２】
【表１７】
2008501185.tif 000018
【００６３】
Ｌｏｏｐ２が表１６より１回多い反復にわたって据え置かれる場合、上記表１７に示す実行順序が実現される。今度は１４反復が行われるが、各反復において、隣接する元の本体間のデータ依存関係はない。
【００６４】
【表１８】
2008501185.tif 000019
【００６５】
部分的依存関係は、普通、依存関係が特定の配列要素まで、よって、特定の反復まで突き止められ得る配列への規則的アクセスから導出され得る。１つのステップは、配列アクセスへの索引を解析することとしてもよい。上記表１８に示す例は、２つのネストされたループ（Ｌｏｏｐ１とＬｏｏｐ２）を有し、配列の索引付けに使用されるループ式を示している。ループ式とは、一般に、ループ内の式がループ反復カウンタの関数である場合に、それを記述するのに使用される用語である。ループが完全に展開されている場合、かかる式は、リテラル定数で置き換えることもできる。線形ループ式とは、一般に、その値がループ反復カウンタの線形関数である、即ち、式の値が、最初の反復では定数値を有し、ループの各反復ごとに、一定量だけ増加し、または減少する式を表す。
【００６６】
Ｃ言語の構文は、配列の各要素へのアクセスを、その配列の１要素を取得するための式
を用いて配列に索引付けすることによって可能にする。多次元配列は、一般に、１次元で配列にアクセスするための適切な式の生成によって、単次元配列に変換され得る。要素は、通常、ビットのブロック（整数値など）である。かかる要素は、普通、独立にアクセスされ得る最小のデータ・チャンクである。ある要素の少数のビットだけしか使用されない場合、その配列要素全体が取得される必要があることもあり、その場合、その時点において、使用されるビットを、その要素と定数との論理積をとる（例えばａ［ｎ］＆１など）、ビット・マスキングという方法によって選択することができる。定数に応じて、式は、ビットだけに依存することもあり、その場合、定数を「１」として、事実上、その他のビットすべてをマスクする。
【００６７】
【表１９】
2008501185.tif 000020
【００６８】
配列アクセス間のデータ依存関係を解析するためには、普通、使用されるビットだけを考慮すべきである。アクセスの粒度は、一般に、要素のチャックとしてのみならず、各ビットごとともすべきである。これは、普通、配列内の各ビットごとに、様々な整合するアドレス指定方式の１つを必要とする。一例では、最下位ビット（ＬＳＢ）が、各要素における最小のビット索引を有することを意味する、「ＢｉｇＥｎｄｉａｎ」アドレス指定方式が使用されてもよい。ある要素が３２ビットを有するものと仮定すると、上記表１９に示すビット・アドレスが使用される。この例の一般的な場合において、Ｗｏｒｄ（ｉ）は、ＭＳＢ：Ｂｉｔ（（ｉ＋１）＊ｗｏｒｄｌｅｎ−１）からＬＳＢ：Ｂｉｔ（ｉ＊ｗｏｒｄｌｅｎ）までのビットからなる。よって、Ｗｏｒｄ（ｉ）と定数ビットマスクとの論理積がとられる場合、ビットマスクの値に応じて、スライスは、更に小さくすることができる。
【００６９】
線形ループ式を索引として用いる配列アクセスは、４つの部分からなる（例えば、Ａｒｒａｙ、Ｂｉｔｐｏｓ、Ｂｉｔｌｅｎ，Ｂｉｔｉｎｃｒからなる）ものとして記述することができ、その場合、Ａｒｒａｙは、アクセスされる配列の名前であり、Ｂｉｔｐｏｓは、最初の反復における右端のビットの索引であり、Ｂｉｔｌｅｎは、アクセスされる連続ビットの数であり、Ｂｉｔｉｎｃｒは、Ｂｉｔｐｏｓが各反復ごとに増加するビット数である。２つのループ間の依存関係を抽出するために、すべての共通変数を抽出することが必要とされることもある。データ依存関係がない場合、各ループは、独立ループとしてマージされ得る。依存関係があるが、その依存関係が、共通の配列によって引き起こされる場合、各ループは、なお、部分的に依存していることがある。潜在的な配列上のアクセスが、４つの部分からなるものとして抽出され得る。どちらかのループ内のアクセスの１つだけが線形ループ式によって索引付けされていない場合、解析は、失敗する可能性が高く、各ループは、おそらく、完全に依存している。そうでない場合、第１のループ内の各アクセスが、第２のループ内の各要素と比較されるはずである。
【００７０】
一例では、（Ａｒｒａｙ、Ｂｉｔｐｏｓ１、Ｂｉｔｌｅｎ１、Ｂｉｔｉｎｃｒ１）と（Ａｒｒａｙ、Ｂｉｔｐｏｓ２、Ｂｉｔｌｅｎ２、Ｂｉｔｉｎｃｒ２）とを、それぞれ、共通配列上の、Ｌｏｏｐ１とＬｏｏｐ２とにおける配列アクセスとする。  まず、各アクセスが、その下で完全に独立である２つの条件がチェックされ得る。第１の条件の下では、ループが、ｆｏｒループによくある、最大反復カウントを有する場合、索引の全範囲が計算され得る。また、Ｂｉｔｉｎｃｒが０である場合には、そのループが最大反復カウントを持たない場合であっても、全範囲が計算され得る。両方のアクセスが全範囲を有し、そ
れらの全範囲が交わらない場合、各アクセスは独立である。ＧＣＤが、その引数の最大公約数である第２の条件の下では、Ｂｉｔｌｅｎ１＋Ｂｉｔｌｅｎ２がＧＣＤ（Ｂｉｔｉｎｃｒ１，Ｂｉｔｉｎｃｒ２）以下であり、（Ｂｉｔｐｏｓ１−Ｂｉｔｐｏｓ２）ｍｏｄｕｌｕｓＧＣＤ（Ｂｉｔｉｎｃｒ１，Ｂｉｔｉｎｃｒ２）が−Ｂｉｔｌｅｎ２からＢｉｔｌｅｎ１までの間の排他的範囲にない場合、各アクセスは、やはり独立である。
【００７１】
これら２つの場合が一致せず、第１のループが最大反復カウントｍａｘＬｏｏｐ１を有する場合、各アクセスは、やはり、部分的に依存している可能性がある。依存関係の度合いは、Ｌｏｏｐ２の最初の反復が開始する前に、Ｌｏｏｐ１が、何反復を完了する必要があるかによって測られ得る。この回数を、反復オフセットと呼んでもよい。反復オフセットが０である場合、各ループは独立であり、オフセットなしでマージされ得る。反復オフセットが、Ｌｏｏｐ１の最大反復数以上である場合、Ｌｏｏｐ１は、Ｌｏｏｐ２が開始される前に完了される必要があり、各ループは、完全に依存している。反復オフセットがこれら２つの値の間にある場合、各ループは、部分的に依存しており、部分的にマージされ得る。
【００７２】
【表２０】
2008501185.tif 000021
【００７３】
この例で必要とされるオフセットを計算するために、上記表２０に示す式が使用され得る。
【００７４】
【表２１】
2008501185.tif 000022
【００７５】
上記表１３に示す例では、両方のループが、配列ｔｍｐにアクセスする。従って、（上記表２１に示すように）配列ｔｍｐへのすべてのアクセスが解析されるべきである。対（Ａ，Ｂ）のオフセットは、０である。というのは、Ｌｏｏｐ２が、同じ反復においてＬｏｏｐ１によって書き込まれる値を読み取るからである。対（Ａ，Ｃ）のオフセットは、１である。というのは、Ｌｏｏｐ２が、１反復後に、Ｌｏｏｐ１によって計算される値を読
み取るからである。対（Ａ，Ｄ）のオフセットは２である。というのは、Ｌｏｏｐ２が、２反復後に、Ｌｏｏｐ１によって計算される値を読み取るからである。よって、この例での合計最小オフセットは、結果として、Ｌｏｏｐ２の前にＬｏｏｐ１を２反復実行する必要があることになる。
【００７６】
（ループ正規化）
ループ・マージにおける１つのステップ例は、すべての影響を受けるループの無条件のｗｈｉｌｅループへの変換を伴い得る。例えば、ｆｏｒループは、普通、ｗｈｉｌｅループに変換することができ、ｗｈｉｌｅループおよびｄｏ−ｗｈｉｌｅループ内の終了条件は、普通、当該の１つまたは複数のループの先頭または末尾の条件付きｂｒｅａｋステートメントで置き換えることができる。これらの変換は、しばしば、対応する言語参照マニュアルの定義から導出され得る。
【００７７】
別の、または代替のステップ例は、ｃｏｎｔｉｎｕｅステートメントとｎｅｘｔステートメントとの処理を伴っていてもよい。マージされたループにおいて、これらのステートメントは、共通のループに適用され、その他の１つまたは複数のループの本体を制御してもよい。複雑さは、すべてのｃｏｎｔｉｎｕｅステートメントおよびｎｅｘｔステートメントを、ｃｏｎｔｉｎｕｅステートメントがなく、多くとも、ループの末尾に１つの条件付きｂｒｅａｋステートメントがあるだけの、指定された正規形にすることによって処理されてもよい。
【００７８】
ｃｏｎｔｉｎｕｅステートメントは、一般に、ループの現在の反復を終了し、直ちに、次の反復を開始する。よって、ｃｏｎｔｉｎｕｅステートメントは、しばしば、フラグ変数を設定し、そのフラグ変数に続くステートメントを条件付きにすることで置き換えられ得る。
【００７９】
ｂｒｅａｋステートメントは、一般に、ループの現在の反復を終了し、そのループを終了する。ｂｒｅａｋステートメントは、しばしば、フラグ変数を設定し、そのフラグ変数に続くステートメントを条件付きにし、単一のｂｒｅａｋステートメントを用いて本体の末尾でそのループを終了することで置き換えられ得る。よって、この最後のｂｒｅａｋステートメントは、ループ内に残される唯一のｂｒｅａｋステートメントとなるはずである。
【００８０】
ループ正規化後、ｂｒｅａｋを終了させる条件が真になるまで、各ループ本体を実行することが望ましいこともある。各ループが独立である場合、各本体は、任意の順序で実行することができ、正しい反復数さえ守られればよい。共通ループは、両方の本体が十分な回数だけ実行されるまで走る必要があるが、その回数は、ループ間で異なり得るため、各本体は、ｉｆステートメントで囲まれることが必要とされ得る。かかるｉｆステートメントは、終了条件が真になった後で、それ以上の反復の実行をブロックすることができる。よって、共通ループは、両方の終了条件が真であるときに終了することができる。
【００８１】
（中間ステートメント）
ループ・マージにおける別のステップ例は、中間ステートメントの移動を含んでいてもよい。例えば、マージされ得るループ間のステートメントが存在していてもよい。かかるステートメントは、プロセスの開始時から存在していてもよいし、ループ正規化の結果として生成されていてもよい。
【００８２】
一例では、マージされるべき２つのループ（例えば、Ｌｏｏｐ１とＬｏｏｐ２など）の間に中間ステートメントがある。この例では、中間ステートメントは、Ｌｏｏｐ１の前、またはＬｏｏｐ２の後に移動されるべきである。中間ステートメントは、Ｌｏｏｐ１に対
するデータ依存関係を持たない場合、Ｌｏｏｐ１の前に移動され得る。何らかの逆依存関係が存在する場合、幾つかの変数を、移動の前に一時変数で置き換えることが必要とされてもよい。中間ステートメントは、Ｌｏｏｐ２に対するデータ依存関係を持たない場合、Ｌｏｏｐ２の後に移動され得る。Ｌｏｏｐ２に対する逆依存関係は、一時変数の作成によって解決され得る。両方のループへのデータ依存関係を有する中間ステートメントは、それらのループが相互にデータ依存し合っており、よって、この例ではマージできないことを意味している。
【００８３】
（ループ展開）
ループ展開は、一般に、ループの本体の複製を含む技法であり、ループ・マージなど、より多くの最適化方法を明示する可能性がある。ループ反復数が決定された後で、ループは、展開制約条件に基づいて展開されてもよい。かかる展開は、ループ反復数を変更させることもある。前に、非マージ可能ループであると初期に識別されたループを展開または部分的に展開すると、そのループが、少なくとも部分的にマージ可能になることもある。また、ループ展開は、ループ反復間の並列性を明示することもある。ループ展開は、例えば、ループが、ループ本体が単に複製されるだけの無条件ｗｈｉｌｅループとして正規化された後で実行することもできる。
【００８４】
部分的展開は、しばしば、展開されたループの１反復が、元のループの２回以上の反復を実行するように、ループの本体が１回または複数回複製される変換を伴う。よって、その新しいループは、同じ機能を、より少ない反復数で実行する。
【００８５】
【表２２】
2008501185.tif 000023
【００８６】
【表２３】
2008501185.tif 000024
【００８７】
一例では、ｉｍｇ＿ｂｕｆｆｅｒへのアクセスはループ反復子だけにしか依存していないにもかかわらず、上記表２２に示すループの何れもマージできない。一実施形態では、上記表２３に示すように、Ｖｅｒｔｉｃａｌループは、２回部分的に展開され、多少のマージが可能な４つのループを生じることが可能である。この例では、ループ展開が、ループ・マージの前に適用される必要がある。というのは、展開前には、マージ可能なループがなく、展開後には、次のような可能性が生み出されているからである。即ち、Ｖｅｒｔｉｃａｌ＿Ｃａｕｓａｌは、Ｖｅｒｔｉｃａｌ＿Ｃａｕｓａｌ＿１またはＶｅｒｔｉｃａｌ＿ＡｎｔｉＣａｕｓａｌ＿１とマージされてもよく、Ｖｅｒｔｉｃａｌ＿ＡｎｔｉＣａｕｓａｌは、Ｖｅｒｔｉｃａｌ＿Ｃａｕｓａｌ＿１またはＶｅｒｔｉｃａｌ＿ＡｎｔｉＣａｕｓａｌ＿１とマージされてもよい。
【００８８】
幾つかの実施形態では、マージの順序が重要である。というのは、２つのループをマージすると、その結果生じるループがマージされなくなることもあるからである。従って、マージするのに最適なループのセットを決定するためのヒューリスティックが適用されてもよい。別のループとマージされ得る各ループに、「エッジ」を付与することもでき、その場合、例えば、最も少数のエッジを除去するマージが選択され、次いで、各エッジが再生成される。結合の場合、一手法では、第１のマージ可能なループが、それがマージされ得る第１のループとマージされる。上記の例では、それは、Ｖｅｒｔｉｃａｌ＿ＣａｕｓａｌがＶｅｒｔｉｃａｌ＿Ｃａｕｓａｌ＿１とマージすることを意味するはずである。
【００８９】
（ループ・パイプライン化）
ループ・パイプライン化は、次のループの反復をどれほどの頻度で開始すべきか決定することを伴う。一実施形態では、ループ・パイプライン化は、ループ・マージをより複雑にするようにループを再構成することを可能にし、そのため、パイプライン化変換は、望ましくは、幾つかの例では、ループ・マージの後で行われてもよい。幾つかの実施形態では、マージが長いフィード・バック・パスを生じない限り、マージされたループが、更に、パイプライン化され得る。かかる実施形態では、第２のマージされたループは、データ依存関係がある場合には、第１のマージされたループの少なくとも１反復の後で開始し得る。
【００９０】
（独立ループ・マージの例）
この項では、開示の技術の多くの可能な実施形態の１つ、より具体的には、独立ループについて詳述する。この例のコードはＣコードである。Ｃは逐次言語であるため、この例では、言語によって実行の順序が厳格に定義される。各ループ本体がどのくらいの頻度で実行されるかは、普通、プログラマにより、ｆｏｒ、ｗｈｉｌｅ、ｃｏｎｔｉｎｕｅ、ｂｒｅａｋといったループ・ステートメントを使って定義される。この例はＣコードで書かれているが、この例の中で適用される方法は、Ｃコードに限定されず、他の同様なプログラミング言語にも適用される。
【００９１】
【表２４】
2008501185.tif 000025
【００９２】
この例で、上記表２４のＣコードは、ｉおよび配列ａ、ｂ、ｘ、ｙおよびｚが別の場所で宣言され、使用されているものと仮定している。実行時に、このコードは、幾つかの計算を実行し、配列ａとｂとに値を代入する。
【００９３】
【表２５】
2008501185.tif 000026
【００９４】
【表２６】
2008501185.tif 000027
【００９５】
この例では、固有の実行順序が、上記表２５に示されている。Ｂｏｄｙ１．Ｎは、ループ本体の繰り返される実行の１つのインスタンスを表し、その第１のインスタンスは索引Ｎ＝０を有する。この例で、Ｂｏｄｙ１は、正確に４回実行され、Ｂｏｄｙ２は、多くとも７回までしか実行されないが、ｂｒｅａｋステートメントは、任意の反復時にこのループを打ち切ることができる。ループ・マージの１つの目標は、マージする前の２つのループと同じ機能を有する単一のループを作成することであるため、マージされたループの所望の実行順序は、上記表２６に示すものと成り得る。
【００９６】
【表２７】
2008501185.tif 000028
【００９７】
この例では、配列ａとｂは、それぞれ、ループの１つで使用されるだけである。その他の配列、ｘとｙとｚとは、読み取られるだけであり、そのため、それらの使用は依存関係を生じない。変数ｉだけが両方のループで書き込まれ、ループ間の依存関係の原因となり得る。更なる解析は、変数ｉの最終の値がＬｏｏｐ２では使用されないことを示している。というのは、Ｌｏｏｐ２は、変数ｉを最初に使用する前に、変数ｉに新しい値を代入するからである。これは、データ依存関係がなく、Ｌｏｏｐ２においてｉをｉ２で置き換えることによって共通の使用が解決され得ることを意味している。かかる変換が、上記表２７に示されている。
【００９８】
【表２８】
2008501185.tif 000029
【００９９】
【表２９】
2008501185.tif 000030
【０１００】
【表３０】
2008501185.tif 000031
【０１０１】
次に、望ましくは、前述のように、正規化技法が、この例に適用される。正規化の第１のステップは、例えば、各ループを、無条件のｗｈｉｌｅループに変換して、上記表２８に示す変更されたコードを生じることを伴う。この例のこの時点において特に注目すべきことは、ｆｏｒループをｗｈｉｌｅループに変換するときに、各ｃｏｎｔｉｎｕｅステートメントの前に、ループ増分の実行が必要とされ得ることである。この例における任意選択のステップが、Ｌｏｏｐ２を展開することである。表２９（上記）には、２回展開された後のＬｏｏｐ２が示されている。正規化の第２のステップは、ｃｏｎｔｉｎｕｅ、ｎｅｘｔ、ｂｒｅａｋといったステートメントを処理して、上記表３０に示す変更されたコードを生じることを伴う。
【０１０２】
【表３１】
2008501185.tif 000032
【０１０３】
次のステップは、中間ステートメントの潜在的移動を調査することである。この例では、ステートメント「ｉ２＝８」と「ｂｒｅａｋ＿ｌｏｏｐ２＝ｆａｌｓｅ」がＬｏｏｐ１を越えて移動されて、上記表３１に示す変更されたコードを生じる。というのは、ｉ２とｂｒｅａｋ＿ｌｏｏｐ２はＬｏｏｐ１では使用されないからである。今や、各ループは、マージされることが可能な状態である。
【０１０４】
【表３２】
2008501185.tif 000033
【０１０５】
これら２つのループをマージすると、上記表３２に示す変更されたループがもたらされる。
（第１の依存ループ・マージの例）
この項では、開示の技術の多くの可能な実施形態の別の１つ、より具体的には、依存ループについて詳述する。
【０１０６】
【表３３】
2008501185.tif 000034
【０１０７】
一例では、上記表３３に示すコードを使って、Ｌｏｏｐ１がデータを計算し、そのデータを配列ｔｍｐに格納する。次いで、データの値が、更なる計算のために、Ｌｏｏｐ２で使用される。
【０１０８】
【表３４】
2008501185.tif 000035
【０１０９】
この例の第１のステップは、前述の正規化技法の適用である。各ループの変換は、上記表３４に示す変更されたコードを生じる。独立ループ・マージとの１つの違いが、ここで明示されており、それは、Ｂｏｄｙ２の第１の反復が直ちに開始され得ず、Ｂｏｄｙ１の何回かの反復が実行されるまで据え置かれる必要があるという点である。据え置くべき反復数は、依存関係解析からもたらされ、それは、この例では、３である。
【０１１０】
【表３５】
2008501185.tif 000036
【０１１１】
ある一定の反復数の間Ｂｏｄｙ２をブロックすることは、ブロックすべき反復数で初期設定されるカウンタ変数を持つことによって実現され得る。かかる変数は、それが０に達するまで、各反復ごとに減分することができ、それ以降、Ｂｏｄｙ２を実行することが可能になり、結果として、上記表３５に示すマージされたループを生じる。
【０１１２】
第２の依存ループ・マージの例
この項では、開示の技術の多くの可能な実施形態の別のもの、より具体的には、部分的中間操作を有する依存ループについて詳述する。
【０１１３】
【表３６】
2008501185.tif 000037
【０１１４】
上記表３６に示す例では、中間操作「ｔｍｐ［４］＝ｔｍｐ［９］」は、両方のループに対するデータ依存関係を有し、よって、ループの一方を越えて移動され得ない。マージされたループにおいて、この操作は、ある特定の反復において実行される必要がある。この例では、第１のループの反復９（ｉ＝９）の後、第２のループの反復３（ｊ＝３）の前に実行される必要がある。
【０１１５】
【表３７】
2008501185.tif 000038
【０１１６】
例において、各ループをマージし、中間操作を特定の反復にバインドするためには、据え置き／カウンタ変数（ｄｅｆｅｒ＿ｃｎｔ）が、正のループ反復数をカウントするように拡張され、その値が、中間操作を、それが正しい反復にあるときに、正確に実行するための条件として使用されるようにする必要がある。ループをマージすると、上記表３７に示す単一のマージされたループが生じる。
【０１１７】
（動作合成ツールのユーザとの対話）
幾つかの回路設計では、マージされ得る（例えば、マージ可能である）すべてのループをマージすることが望ましい。一実施形態では、動作合成ツールが、ユーザによって設定されるマージ可能ディレクティブに基づいて一部または全部のマージ可能なループをマージするように設定され得る。加えて、マージ可能ディレクティブは、デフォルト値に設定されてもよい。例えば、マージ可能ディレクティブは、個別のマージ可能なループごとに許可を求めることなく、すべてのマージ可能なループがマージされてもよいことを意味する、真のデフォルト値に設定されてもよい。ユーザが、ツールを、マージ可能なループを自動的にマージしないように設定しようとする場合には、ユーザは、マージ可能ディレクティブを偽に変更することによってそのように設定してもよい。一実施形態では、マージ可能ディレクティブは、グラフィカル・ユーザ・インターフェース（ＧＵＩ）を介して設定され、または変更されてもよい。
【０１１８】
マージ可能ディレクティブに加えて、動作合成ツール・ユーザが、ある設計内のマージ可能なループをマージすることが、その設計の他の部分にどんな影響を及ぼし得るか知ることが望ましい場合もある。一実施形態では、動作合成ツールが、ユーザに、マージ可能なループのマージが設計に及ぼし得る影響を示す。以下の２つの表は、生成され得るレポートの実例を示すものである。
【０１１９】
【表３８】
2008501185.tif 000039
【０１２０】
【表３９】
2008501185.tif 000040
【０１２１】
マージ可能なループをマージしないことによる影響を詳述するために上記表３８に示すようなレポートが生成され、マージ可能なループをマージすることによる影響を詳述するために表３９に示すようなレポートが生成され得る。
【０１２２】
かかる記述は、ユーザによって、例えば、ツールのＧＵＩなどを介して出される特定の要求に応答して提供されてもよい。別の実施形態では、かかる記述は、マージ可能ディレクティブが真に設定されているときにはいつでも、ユーザによって指示されなくとも、提供される。代替として、ユーザは、ツールを、ユーザによって特に要求されない限りかかる記述を提供しないように設定することもできる。
【０１２３】
（分散コンピュータ・ネットワーク）
前述の技術の態様の何れも、分散コンピュータ・ネットワークを使って実行され、または設計されてもよい。図４に、かかるネットワークの例を示す。サーバ・コンピュータ４００は、（サーバ・コンピュータに内蔵され、または外付けされている）関連付けられた記憶装置４０２を備えることができる。例えば、サーバ・コンピュータ４００は、（ＥＤＡソフトウェア・ツールの一部などとして）前述の実施形態の何れかを使って回路設計を処理するように構成され得る。サーバ・コンピュータ４００は、４０４に一般的に示すネットワークに結合されていてもよく、このネットワークは、例えば、広域ネットワーク、ローカル・エリア・ネットワーク、クライアント／サーバ・ネットワーク、インターネット、あるいは他の同様な類似のネットワークなどを含むことができる。４０６と４０８に示すような、１つまたは複数のクライアント・コンピュータが、ネットワーク・プロトコルを使ってネットワーク４０４に結合されていてもよい。
【０１２４】
（データベース変更）
図５は、設計情報（ネットリストなど）を含むデータベースが、図４に示すサーバ・コ
ンピュータ４００などのリモート・サーバ・コンピュータを使って、本明細書で開示する実施形態の何れかに従って合成された回路の設計情報を含むように更新され（または変更され）得ることを示している。プロセス・ブロック５００で、例えば、クライアント・コンピュータは、回路に関連する設計データを送る。例えば、クライアント・コンピュータは、ネットリストまたはその他のＥＤＡ設計データベースを送ってもよい。  プロセス・ブロック５０２で、サーバ・コンピュータによって、データが受け取られ、ロードされる。
【０１２５】
プロセス・ブロック５０４で、データベースによって定義された回路は、開示の実施形態の何れかに従って処理される。次いで、結果として生じた設計を表す新しいデータベースが作成され得る。この新しい設計データは、設計データベースの更新（または変更）バージョンとして、あるいは１つまたは複数の別個のデータベースとして格納され得る。
【０１２６】
プロセス・ブロック５０６で、サーバ・コンピュータは、更新されたデータベースまたはその他のデータベースをクライアント・コンピュータに送り、クライアント・コンピュータは、プロセス・ブロック５０８でそのデータベースを受け取る。図５に示す例は、関連する設計データを含めるように設計データベースを更新する唯一の方法ではないことが、当分野の技術者には明白なはずである。例えば、設計データは、ネットワーク上にはなく、サーバに別に送られるコンピュータ可読媒体に格納されてもよい。あるいは、サーバ・コンピュータは、設計手順の一部分だけを実行してもよい。
【０１２７】
以上、本発明の原理を、幾つかの実施形態によって図示し、説明したが、それらの実施形態の構成および詳細が、本発明の原理を逸脱することなく変更され得ることは、明白なはずである。前述の実施形態は、例示のためのものにすぎず、本発明の範囲を限定するものと解釈されるべきではない。本発明は、添付の特許請求の範囲およびその均等物の範囲と精神とに含まれ得るかかるすべての実施形態を包含するものである。
【図面の簡単な説明】
【０１２８】
【図１】集積回路を生成するシステムの例を示すブロック図である。
【図２】図１に示すシステムなど、ハードウェア設計ツールに従って集積回路を生成する方法の例を示す流れ図である。
【図３】集積回路を生成するより詳細な方法の例を示す流れ図である。
【図４】開示の方法を実行する際に使用され得るクライアント／サーバ・ネットワークを示すシステム図である。
【図５】例えば、図４のネットワークなどを使ったデータベースの作成を示す流れ図である。
【図１】
2008501185.tif 000041
【図２】
2008501185.tif 000042
【図３】
2008501185.tif 000043
【図４】
2008501185.tif 000044
【図５】
2008501185.tif 000045
【国際調査報告】
2008501185.tif 000046
2008501185.tif 000047
2008501185.tif 000048