(57)【要約】  【課題】  プロセッサ資源管理をアセンブラ言語に組込むためのシステムおよび方法の提供。  【解決手段】  アセンブラを用いてコードをアセンブルするための方法およびシステムが開示される。アセンブラ言語コードは、変数といった資源要求および、レジスタ、入出力ロケーション、記憶場所、コプロセッサといった資源と関係づけられた複数のコードブロックを含む。方法およびシステムは、実行時資源競合が回避されるような資源に対する資源要求の大域的割当てを可能にする技術を提供することを含む。方法およびシステムはさらに、資源が定義および管理されることを可能にするための文法、資源要求が定義および管理されることを可能にする文法、コードブロックの定義を付与する文法、および資源をコードブロックと関係づけるための文法を提供することを含む。  【選択図】      図３
2004220583.tif 000002
【特許請求の範囲】
【請求項１】
アセンブラを用いてアセンブラ言語コードをアセンブルする方法であって、コードは複数のコードブロックを含んでおり、複数のコードブロックは複数の資源要求を有し、複数のコードブロックは複数の資源を有しており、方法は、
（ａ）文脈、複数の資源要求および複数の資源を認識する工程と、
（ｂ）文脈に基づいて複数の資源の少なくとも一部を自動的に割当てる工程と、複数の資源は文法を用いて定義および管理され、複数の資源の少なくとも一部は、実行時に同じ資源を使用する２つの文脈が同時にまったく存在しないように、複数の資源のメンバを複数の資源要求と対にすることによって割当てられ、
（ｃ）複数の資源要求の全部が複数の資源から割当てられた場合、アセンブラ言語コードに基づいて実行可能イメージを生成する工程とを含む、方法。
【請求項２】
自動的に割当てる工程（ｂ）は、
（ｂ１）複数の資源のうちのいずれも複数の資源要求に自動的に割当てることができなければ、複数の資源要求のうちのいずれが複数の資源の少なくとも１つも割当てられていないかを指示する工程をさらに含む、請求項１の方法。
【請求項３】
アセンブラを用いてアセンブラ言語コードをアセンブルする方法であって、コードは複数のコードブロックを含んでおり、複数のコードブロックは複数の資源要求を有し、複数のコードブロックは複数の資源を有しており、方法は、
（ａ）文脈を指定するための第１の文法を付与する工程と、
（ｂ）文脈と関係づけられた複数の資源要求を指定するための第２の文法を付与する工程と、
（ｃ）文脈と関係づけられた複数の資源を指定するための第３の文法を付与する工程と、
（ｄ）文脈内での間接的資源の使用または資源要求の間接的使用の曖昧性を解決するための第４の文法を付与する工程と、
（ｅ）文脈内での間接的制御フロー変更の曖昧性を解決するための第５の文法を付与する工程と、
（ｆ）実行時に同時に存在する複数の文脈の一部が同じ資源を使用しないように複数の資源のメンバを複数の資源要求と対にすることによって複数の資源の少なくとも一部を自動的に割当てる工程とを含む、方法。
【請求項４】
（ｇ）複数のコードブロックの資源使用を認識する工程をさらに含む、請求項３の方法。
【請求項５】
（ｇ）複数の資源のうちのいずれも複数の資源要求に自動的に割当てることができなければ、複数の資源要求のうちのいずれが複数の資源の少なくとも１つも割当てられていないかを指示する工程をさらに含む、請求項３の方法。
【請求項６】
資源割当て工程（ｆ）は、
（ｆ１）複数の頂点および複数の頂点を結合する複数の辺を含む資源割当てグラフを用いて割当てを行う工程をさらに含み、複数の頂点の各々は複数のコードブロックのうちのコードブロックによる資源要求の使用に対応しており、１対の複数の頂点を結合する複数の辺の各々は共存する資源要求を表現している、請求項３の方法。
【請求項７】
資源割当て工程（ｆ）は、
（ｆ２）共通の辺を共有している複数の頂点のメンバが異なる資源を使用するように、複数の資源の一部を資源割当てグラフにおける複数の頂点に割当てる工程をさらに含む、請求項６の方法。
【請求項８】
割当て工程（ｆ２）は、
（ｆ２ｉ）頂点によって表現された資源要求がアクティブである文脈の数に基づいて複数の頂点のそれぞれに重みを付与する工程と、
（ｆ２ｉｉ）複数の頂点のそれぞれの重みに基づく順序で資源を複数の頂点に割当てる工程とをさらに含む、請求項７の方法。
【請求項９】
（ｇ）資源割当てグラフにおける複数の頂点のいずれも資源を割当てることができない場合、複数の資源要求のうちのいずれが、共通の辺を共有している複数の頂点のメンバが異なる資源を使用するように割当てることができないかを指示する工程をさらに含む、請求項８の方法。
【請求項１０】
アセンブラ言語コードを処理するアセンブラであって、アセンブラ言語コードは複数のコードブロックを含んでおり、複数のコードブロックは複数の資源要求を有する複数の資源を使用するものであり、アセンブラは、
アセンブラ言語コードを読込み、文脈を認識し、複数の資源要求の宣言および使用を認識し、複数の資源の宣言および使用を認識するためのパーサおよびレクサと、
コードに基づいて実行可能イメージを生成するためのコードジェネレータと、
文脈に基づいて複数の資源の少なくとも一部を自動的に割当てるための資源マネージャとを含み、複数の資源は文法を用いて定義および管理され、複数の資源の少なくとも一部は、実行時に同じ資源を使用する２つの文脈が同時にまったく存在しないように、複数の資源のメンバを複数の資源要求と対にすることによって割当てられる、アセンブラ。
【請求項１１】
資源マネージャは、複数の資源が複数の資源要求に自動的に割当てることができなければ、複数の資源要求のうちのいずれが複数の資源のうちのメンバを割当てることができないかを指示する、請求項１０のアセンブラ。
【請求項１２】
資源マネージャは、複数の頂点および複数の頂点を結合している複数の辺を含む資源グラフを使用することによって複数の資源の一部を割当て、複数の頂点の各々は複数の資源要求の使用に対応しており、複数の辺の各々は１対の共存する資源要求に対応している、請求項１０のアセンブラ。
【請求項１３】
資源マネージャはさらに、共通の辺を共有している複数の頂点のいずれも複数の資源のうちの異なる資源を割当てられるように、複数の資源の一部を複数の頂点に割当てる、請求項１２のアセンブラ。
【請求項１４】
資源マネージャは、頂点によって表現される資源要求が存在する文脈の数に基づいて複数の頂点のそれぞれの重みによって誘導される資源グラフにおいて複数の資源のうちの資源を複数の頂点に割当てる、請求項１３のアセンブラ。
【請求項１５】
資源マネージャはさらに、複数の頂点のうちのいずれが、共通の辺を共有している頂点が複数の資源のうちの異なる資源を割当てられるように複数の資源のうちの資源を割当てることができないかを指示する、請求項１４のアセンブラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータシステム、詳細には、アセンブラによってプロセッサ資源を大域的に割当てるための方法およびシステムに関する。
【背景技術】
【０００２】
アセンブラ言語コードは、多様なアプリケーションにおいて使用されている。アセンブラ言語コードから実行可能イメージを生成するために、一般に従来のアセンブラが使用される。図１は従来のアセンブラ１０を図示している。従来のアセンブラ１０は、アセンブラ言語コードを読込むためのパーサ／レクサ１２および、実行可能イメージを生成するためのコードジェネレータ１４を含む。アセンブラ１０は、パーサ／レクサ１２に続けてコードジェネレータ１４を逐次的に呼び出す。
【０００３】
図２は、従来のアセンブラ１０を用いてアセンブラ言語コードから実行可能イメージを生成するための従来の方法５０を図示する高水準流れ図である。コード内の要求を満たす資源は、ステップ５２によってプログラマによって手作業で割当てられる。アセンブラ言語コードはその後、ステップ５４を経て１０によってアセンブルされる。実行可能イメージがこうして付与される。ステップ５４からの実行可能イメージは、ステップ５６を経て資源競合を含む問題について分析される。資源競合が存在する場合、ステップ５８がステップ５２において手作業での資源の別の割当てを強制する。ステップ５２、５４、５６および５８のサイクルは、資源競合または他の欠陥がまったく見つからなくなるまで続けられ、それによって最終的な実行可能イメージを実現する。
【０００４】
当業者は、方法５０が具体化するのに時間がかかる相対的に難しいものとなり得ることを容易に認識するであろう。特に、プログラマは、使用される資源をコードによって手作業で管理し、実行可能イメージの実行時環境において資源競合をデバッグしなければならない。この問題の最も一般的な解決策は、“Ｃ”または“ＢＡＳＩＣ”といった高水準プログラミング言語に移すことである。しかし、プログラマは、高水準言語によって提供される資源管理を得るために、アセンブラ言語によって提供される細密な制御を譲り渡さなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
アセンブラ言語プログラミングによって提供されるプロセッサの細密な制御を犠牲にしたくないそうしたプログラマにとって、必要なものは、プロセッサ資源管理をアセンブラ言語に組込むためのシステムおよび方法である。本発明はそのような要請に対処する。
【課題を解決するための手段】
【０００６】
本発明は、アセンブラを用いてコードをアセンブルする方法およびシステムを提供する。アセンブラ言語コードは、複数の資源要求および複数の資源に関係づけられた複数のコードブロックを識別する。本方法およびシステムは、実行可能イメージにおける実行時資源競合を回避するために、複数の資源要求が個々のコードブロックについて複数の資源のメンバと対にされることを可能にする技術よりなる。本方法およびシステムはさらに、複数の資源が定義および管理されることを可能にするための文法、複数の資源要求が定義および管理されることを可能にするための文法、コードブロックの定義を付与するための文法および、複数の資源および複数の資源要求をコードブロックと関係づけるための文法を含む。本方法およびシステムはさらに、実行可能イメージにおける実行時資源競合が回避されるような形で複数の資源要求のメンバを複数の資源と自動的に対にするための手段を含む。
【発明の効果】
【０００７】
ここに開示されたシステムおよび方法によれば、本発明は、アセンブラを用いて資源を資源要求に自動的に割当てるための方法およびシステムを提供する。さらに、本方法およびシステムはまた、資源が割当てできない場合、適切に失敗し、訂正され得るコードの部分を指示する。その結果、コードのアセンブルは、資源の自動的な分析および割振り、およびビルド時に資源管理問題を解決することによって簡素化される。
【発明を実施するための最良の形態】
【０００８】
本発明は、コンピュータシステムのためのアセンブラ言語およびアセンブラの改良に関する。以下の説明は、当業者が本発明を実施使用することを可能にするために提示されており、特許出願およびその要求条件の文脈において与えられている。好ましい実施形態に対する様々な修正は、当業者には容易に明白となるはずであり、ここでの一般的な原理は他の実施形態にも適用できる。従って、本発明は、示された実施形態に限定されるように意図されておらず、ここに記載された原理および特徴に合致する最も広範な範囲が許されるべきである。
【０００９】
本発明は、アセンブラを用いてアセンブラ言語コードで資源割当てを実行するための方法およびシステムを提供する。アセンブラ言語コードは、複数の資源要求および複数の資源に関係づけられた複数のコードブロックを含む。方法およびシステムは、コードブロックを定義し、コードブロック間の関係のマップを付与し、複数の資源および複数の資源要求を個々のコードブロックと関係づけるための文法を一緒に提供する。方法およびシステムはまた、コードブロックの連係に基づき複数の資源要求のメンバに複数の資源の少なくとも一部を自動的に割当てる。
【００１０】
本発明は、特定の資源、資源要求およびコードブロックについて説明する。しかし当業者は、この方法およびシステムが、アセンブルされるコード、他のより複雑なコードブロックおよび他のコード生成ツールによって使用される他の、かつ／または付加的な資源についても効果的に動作するはずであることを容易に認識するであろう。例えば、本発明の大半はレジスタ割当ての文脈で説明される。しかし、本発明は、以下に限らないが、入出力ロケーション、記憶場所、およびコプロセッサの制御といった他の資源の割当てにも十分に適用可能である。
【００１１】
より具体的には、最も重要なアセンブラ言語の資源管理問題、レジスタ割当てを検討する。ここに記載する方法およびシステムを使用することにより、以下の能力が得られる。
１）高水準言語と同様にしてコードを文脈にグループ化し、文脈情報構造を各文脈と関係づける。
２）アセンブラ言語資源要求／変数の生成を準備し、文脈と適切な文脈情報構造の資源要求／変数との間の連係を記録する。
３）適切な文脈情報構造の文脈とともに資源要求／変数の使用を認識および記録する。
４）サブルーチン呼出しやジャンプといった他の文脈への可能なアセンブラ言語制御フロー変更を認識する。初期および最終の文脈情報構造の制御フロー変更による連係を記録する。
５）適切な文脈情報構造の文脈内での資源／レジスタの使用を認識および記録する。
６）文脈情報構造の文脈内でどのような資源／レジスタが使用可能であるかのインクリメンタルなまたは完全な仕様を準備する。
７）２つ以上の文脈が異なる資源要求／変数に同じ資源／レジスタを同時に使用しないような形でプロセッサ資源／レジスタをアセンブラ言語資源要求／変数に割当てるかまたは、最も少ない資源要求／変数が割当てられないままであるような形で資源／レジスタを割当てることに失敗し、それらの未割当ての資源要求／変数を報告する。
【００１２】
本発明に従った方法およびシステムをより詳細に例証するために、ここで、アセンブルされるコードに資源／レジスタを自動的に割当てることができるアセンブラ１００の１実施形態を図示している図３について説明する。アセンブラ１００は、パーサ／レクサ１０２、コードジェネレータ１０４および資源マネージャ１０６を含む。パーサ／レクサ１０２は、アセンブラ１００に入力されたアセンブラ言語コードを処理する。パーサ／レクサ１０２は、必要な情報をコードジェネレータ１０４および資源マネージャ１０６に供給する。次に、資源マネージャ１０６は、パーサ／レクサ１０２によって見つけられた個々の資源要求／変数に資源／レジスタを可能な最大限まで自動的に割当てる。割当てが失敗した場合、資源マネージャ１０６は、最も少ない未割当ての資源要求／変数をプログラマに報告する。資源要求／変数への資源／レジスタの割当てが成功したと仮定すれば、資源／レジスタ・資源要求／変数ペアリング情報がコードジェネレータ１０４に転送されて、その結果、実行可能イメージ生成が従来通りに行われ得る。
【００１３】
図４は、資源が自動的に割当てられることを可能にするための本発明に従ったアセンブラ１００の実施形態を用いてアセンブラ言語コードから実行可能イメージを生成するための方法２００を図示している流れ図である。動作時、アセンブラ１００は、ステップ２０２によって資源／レジスタの割当てを実行し試みる。ステップ２０２は、実行時に同じ資源／レジスタを使用する２つの文脈がいっさい同時に存在しないように資源／レジスタを資源要求／変数と自動的に対にすることを試みる。実行可能イメージにおいて実行時資源／レジスタ競合を生じることなく全部の資源要求／変数に資源／レジスタを割当てることが可能であれば、アセンブラ１００は、ステップ２０４によってアセンブルが成功したと判断する。このようにして、実行可能イメージはステップ２０６によって生成される。ステップ２０４において資源／レジスタ競合が起こり、従ってそのアセンブルが失敗したと判断された場合、アセンブラ１００は、ステップ２０８によって未割当ての資源要求／変数および個々の未割当ての資源要求の関係する文脈を指示する。プログラマはその後、ステップ２１０によって必要とされる資源／レジスタを解放できる。ステップ２１０がインクリメンタルなステップであり、ステップ５２において要求されたような資源の大域的再割当てではなく、従ってアセンブラ言語プログラマの側にそれほど多くない労力を求めることに留意されたい。資源マネージャ１０６は、未割当ての資源要求が、割当てが失敗した文脈２１０の資源／レジスタをプログラマに解放させることによって容易に満たされるような形でステップ２０８を実行する。これは、アセンブルが誤りなく完了できるまで、ステップ２０２、２０４、２０８および２１０が繰り返されることを可能にする。ここでわかるように、プログラマは、コードによって使用される資源の全部を再割当てしなくてよい。代わりにプログラマは、自動的に割当てできなかった資源を解放することに関するより限定的な問題に直面する。これはステップ５２、５４および５６の自動化を結果的にもたらし、従ってアセンブラ言語でプログラムするために必要なプログラミング労力を著しく低減する。
【００１４】
パーサおよびレクサ１０２が本発明に従った方法およびシステムを具体化するために、従来のアセンブラは修正される。一般に、これらの修正は、パーサおよびレクサ１０２が文脈を認識し、資源要求／変数を宣言および認識し、資源／レジスタを宣言および認識することを可能にする。これらの修正は以下を含む。
１）文脈の認識を追加する。一般にこれは、Ｃプログラミング言語の“｛”および“｝”の使用といった文法を追加することによって行われる。
２）資源要求／変数を宣言するために指示語を追加し、これらの資源要求／変数を記録するために内部アセンブラ文脈情報構造を更新する。
３）資源要求／変数または問題の資源要求／変数を記録するために演算コード構造を修正することを含め、演算コード指示語における資源要求／変数の使用の認識を追加する。
４）資源／レジスタを宣言するために指示語を追加し、これらの資源／レジスタの可用性を記録するために内部アセンブラ文脈情報構造を更新する。
５）演算コード指示語における資源／レジスタの使用の認識を追加し、これらの資源／レジスタの使用を記録するために内部アセンブラ文脈情報構造を更新する。
６）曖昧な実行時決定制御フロー変更をアセンブラに知らせるためにプログラム定義言語（ＰＤＬ）指示語を追加し、他の文脈への全部の可能な制御フロー変更を記録するために文脈情報構造を更新する。
７）資源／レジスタアクセスの曖昧な実行時決定をプレフィックスするためにＰＤＬ指示語を追加し、これらの資源／レジスタの使用を記録するために内部アセンブラ文脈情報構造を更新する。
【００１５】
図５は、本発明に従った方法およびシステムの１実施形態の使用を例示する例示的なコード２１５の一部を図示している。例示的コード２１５において、文脈のネストされた集合が見られる。ファイル文脈１Ｃはサブルーチン文脈１Ａを保持し、後者は転じてwhileループ文脈１Ｂを保持する。文脈を管理するための文法は、サブルーチン文脈１Ａの場合と同様、アセンブラの言語と統合され得るか、または文脈管理文法は、転じてwhileおよびendwhile指示語によって区切られている文脈１Ｂによって指示されるように、基本アセンブラ文法とは別個とすることができる。
【００１６】
例示的コード２１５はまた、資源要求／変数管理も例証している。文脈１Ｂにおいて、資源要求／変数２Ａ（TmpVar）が定義される。同様に、資源要求／変数２Ｂ（MyVarlおよびTotalVar）が文脈１Ａにおいて定義される。全部の資源要求／変数２Ａおよび２Ｂが文脈１Ｂにおいてアクティブなので、別個のレジスタが個々の変数に要求されるはずである。また、２Ｃ（ErrReg）によって例示された通り、ファイル文脈１Ｃにおいて資源要求／変数を有することが可能である。
【００１７】
例示的コード２１５はまた、資源／レジスタ管理も例証している。資源要求／変数管理と同様、資源／レジスタ管理も文脈ごとに基づいて行なわれる。ファイル文脈、文脈１Ｃにおいて、非レジスタ資源（メモリ）は４Ａ（ClpArray0）で使用可能にされている。資源４Ａはファイル文脈１Ｃの全部の文脈に使用可能である。文脈１Ａにおいて、４Ｂによって３つのレジスタが使用可能資源のリストに追加される。
【００１８】
また、アセンブラ１００は、例示的コード２１５における資源要求／レジスタの使用も認識する。文脈１Ｂにおいて、同じ文脈（TmpVar）および、現在の文脈（ChangeValueおよびMyVarl）の外側からの資源要求／変数が３Ａにおいて使用される。同様に、プログラマが資源を直接使用することが可能である。これは、メモリ資源ClpArray0が使用されている５Ａに例示されている。
【００１９】
ほとんどのマイクロプロセッサはブランチングにおける実行時決定をサポートしているので、曖昧性を解決し、文脈間の可能な結合をアセンブラに指示するためにアセンブラ文法が付与されなければならない。６Ａにおいて、変数ErrRegは、実行時分岐を行うために使用されている。先行するＰＤＬ指示語は、ErrRegがIPv6ErrorまたはIPv4Errorによって指示されたコード位置のどちらか一方に行くことができるということをアセンブラ１００に知らせる。同様にして、ほとんどのマイクロプロセッサはまた、間接メモリアクセスを行うことが可能である。７Ａでは、アクセスされる記憶場所が曖昧である。この曖昧性は、曖昧な記憶場所が０ｘ１２３４である、または０ｘ４４４４から０ｘ４４５０までのロケーションの範囲にあることを指示することによって先行するＰＤＬ指示語において解決される。
【００２０】
パーサ／レクサ１０２がアセンブラ言語コードの処理を完了した後、資源マネージャ１０６は文脈情報構造の集合を有する。文脈情報構造は、文脈の資源要求／変数および文脈で使用された資源／レジスタならびに、文脈間での可能な制御フロー変更を指示する。
【００２１】
資源マネージャ１０６は、資源／レジスタを資源要求／変数と対にする資源管理アルゴリズムを具体化している。資源マネージャ１０６は、いかなる２つの同時にアクティブな文脈も同じ資源／レジスタを異なる資源要求／変数に使用しないように、資源／レジスタのメンバを資源要求／変数と対にする。資源要求／変数の全部が競合を生じることなく既存の資源／レジスタによって満たされ得ない場合には、資源マネージャ１０６は、資源／レジスタが割当てられない資源要求／変数をプログラマに指示する。この割当ての結果はその後、コードジェネレータ１０４に渡され、そこで資源要求／変数は資源／レジスタによって置換される。
【００２２】
資源マネージャ１０６によって具体化されたアルゴリズムは、いくつかの重要な特性を有する。資源マネージャ１０６は、以下を試みる。
１）資源の使用を最小限にする
２）最も頻繁にアクティブな資源要求に資源を最初に割当てる
３）資源の自動割当てが失敗した時を検出し、資源が割当てられなかった資源要求について報告する。
【００２３】
図６は、アセンブラ１０をアセンブラ１００に変換するための方法２２０の１実施形態の高水準流れ図を図示している。ステップ２２２によってコードブロックが文脈によってグループ化されることを可能にする文法が付与される。従って、ステップ２２２において付与された文法は、文脈がコードブロックについて定義されることを可能にする。ステップ２２２において付与された文法はまた、好ましくは、文脈と関係づけられた資源要求／変数が定義されることを可能にする。また、ステップ２２４によって付与される文法が、好ましくは、文脈内での間接的資源／レジスタの使用または間接的資源要求／変数の使用の曖昧性を解決させることを可能にし、文脈内での間接的制御フロー変更の曖昧性を考慮する。他の文脈への制御フロー変更を記録できる能力は、ステップ２２６によって付与される。資源を定義および管理させることを可能にする文法がステップ２２８によって付与される。従って、プログラマは、パーサおよびレクサの機能を開発するためにステップ２２２、２２４、２２６および２２８において付与された文法を活用することができる。資源を自動的に割当てるための手段がステップ２３０によって付与される。このようにして、ステップ２３０は資源マネージャ１０６を付与する。
【００２４】
図７は、アセンブラ１００といったアセンブラを用いて資源／レジスタを割当てるための本発明に従った方法２５０の好ましい実施形態の流れ図である。方法２５０もまた、好ましくは、資源マネージャ１０６を用いて具体化される。資源／レジスタ割当ては、最初にステップ２５２において、個々の可能な文脈に対応する行および、全部の可能な資源要求／変数に対応する列を備える表を構築することによって実行される。この表は、パーサ／レクサ１０２によって作成された個々の文脈情報構造を調べ、文脈がアクティブである間にアクティブな各資源要求／変数の項目をマークすることによって埋められる。これを行うには、同時にアクティブである他の文脈を突き止め、それらの資源要求／変数を現在の文脈／行の項目に追加するために文脈情報構造の文脈変更情報レコードを使用することが必要であろう。１つの付加的な行が表の最下位に追加される。この行は各列のマークのカウントを含む。このカウントは資源要求／変数がアクティブである回数である。
【００２５】
次に、ステップ２５４において、表は（数学のグラフ理論分岐からの概念を利用する）グラフに変換される。グラフの個々の頂点は、資源要求／変数に対応し、円で図形的に図示される。個々の頂点は辺によって結合され、それは２つの頂点を結合する線で図形的に図示される。グラフの辺は、文脈においてアクティブな１対の資源要求／変数を結合することによって作成される。辺は、文脈において一意の資源要求／変数の全部の可能なペアリングについて作成される。言い換えれば、辺は表の行における一意のマーク間で作成される。
【００２６】
次に、ステップ２５６において、グラフは、結合辺を有するいずれの隣り合う頂点も同じ資源／レジスタが割当てられないように資源／レジスタを割当てるために使用される。本発明の好ましい実施形態において、資源割当ては、赤／黒グラフ切断アルゴリズムの特殊に設計された変種により行われる。この切断アルゴリズムでは、１対の資源／レジスタが、一般にプログラマが通常行う割当て（最も頻繁に使用される資源要求／変数が最初に割当てられる）を模倣し、グラフにおける最大数の辺を切断するように設計された方式で資源要求／変数に割当てられる。この切断アルゴリズムの効果は、個々の対の資源／レジスタが適用される際に、グラフをより小さい分離グラフに分解することである。これは、各分離グラフが同じ資源／レジスタ対を使用することができるので、要求される資源／レジスタの数を最小限にする効果を有する。
【００２７】
図８は、資源／レジスタを資源要求／変数に割当てるための本発明に従った方法２６０の１実施形態を図示している流れ図である。方法２６０は、好ましくは、図７に図示された方法２５０のステップ２５６を実行するために使用される。方法２６０もまた、好ましくは、資源マネージャ１０６を用いて具体化される。図８に戻れば、資源／レジスタは、ステップ２５４から元のグラフに対で割当てられる。方法２６０は、元のグラフを分離グラフ（いずれの辺も共有していないグラフ）に分割することができる。最初のステップ２６２は、それまで未使用であった１対の資源／レジスタを選定することである。ステップ２６４は、資源／レジスタがそれ以上存在しないためにアルゴリズムが失敗したかどうかを決定する。実際にそうであれば、ステップ２６４は割当てを止め、その結果、図４に図示された方法２００のステップ２０８によってエラーが報告され得る。そうでなければ、ステップ２６６において、置換を伴わず可能な分離グラフの集合からいずれかの分離グラフを選定することによって割当ては続行される。当初、ただ１つだけのグラフが存在するはずである。方法は、ステップ２６８において、選定した資源／レジスタ対を選定したグラフに適用する。ステップ２６８は、選定したグラフへの選定した資源／レジスタ対の使用を検討し尽くす。ステップ２７０は、選定した資源／レジスタ対が資源要求／変数に割当てられた全部の頂点を除去する。また、除去された頂点への全部の辺もステップ２７０で除去される。この最終結果はしばしば、選定したグラフのサブグラフへの分割である。しかし、方法２６０は、ステップ２７４までこれらを分離グラフとはみなさない。しかし、方法２６０を通る以前のパスが分離グラフを残していたかもしれない。選定された資源／レジスタ対が、その資源／レジスタ対が選定された時に存在したサブグラフに適用されなかった場合、ステップ２７２は、未処理であったグラフを処理するためにステップ２６６に移る。これは、全部のサブグラフが選定された資源／レジスタ対で処理されるまで続く。全部のサブグラフが処理されると、ステップ２７４が、残りの頂点を調べ、処理のためにグラフの新しい集合を識別するために使用される。ステップ２７４が処理すべきいずれかのグラフを見つけた場合、ステップ２７６は、残りのグラフに対して残りの資源／レジスタにより方法２６０を始める。それ以上グラフが存在しなければ、方法２６０は全部の資源要求／変数を資源／レジスタに首尾よく割当てた。
【００２８】
図９は、ステップ２６８を具体化するための方法２９０である。選定された資源／レジスタ対が単一のグラフに適用されることになる。開始して、ステップ２９２は、選定された資源／レジスタ対から一方の資源／レジスタを選定する。選択は完全に任意である。ステップ２９４は、選定した資源／レジスタを割当てるために単一の資源要求／変数／頂点を突き止めることを試みる。ステップ２９６は、候補の頂点／資源要求／変数がステップ２９４によって見つかったかどうかを確かめるために確認し、見つかっていなければ、資源／レジスタ対の両方の資源／レジスタについて頂点／資源要求／変数のサーチが行われたかを確かめるために第２の確認３０２が実行される。資源／レジスタ対の両方の資源／レジスタについて候補の頂点／資源要求／変数がまったく見つからなければ、方法２９０の割当ては完了である。全部の要求条件を満たす候補の頂点／資源要求／変数が、新しい選定された頂点／資源要求／変数になる。ステップ２９８は、新しく選定された頂点／資源要求／変数を、選定された資源に割当てる。ステップ３００は、選定された資源を選定された対の他方の資源に変更し、方法２９０はステップ２９４で開始して繰り返す。
【００２９】
図１０および図１１は、ステップ２９４を具体化するための方法３２５の１実施形態を図示している。方法３２５は、選定した資源への割当てのために単一の頂点／資源要求／変数を選定するために使用される方法の好ましい実施形態である。方法３２５は、グラフ切断アルゴリズムの核心として最善に理解され、そうしたものとして、グラフ理論の用語を用いて最善に説明される。方法３２５が最初に実行される時、以前に選定された頂点はまったく存在しないはずである。しかし通常は、以前に選定された頂点が存在するであろう。ステップ３３０は、以前に選定された頂点の存在に基づいて候補の頂点の初期集合を選定させる。ステップ３４０において、考慮すべき候補の頂点の集合は、以前に選定された頂点と辺によって結合された全部の未割当ての頂点に設定される。ステップ３５０では、候補の頂点の集合は、選定されたグラフにおける全部の以前に未割当ての頂点に設定される。ステップ３６０において、選定された資源に以前に割当てられた頂点への辺を有する全部の候補頂点が、候補集合から削除される。これは全部の候補頂点を削除することを可能にする。ステップ３７０はこの生起を検出する。候補頂点がもはや存在しなければ、ステップ４７０は、以前に選定された頂点と結合された適格な頂点がまったく存在しなかったためにステップ４７０が生起した場合、方法３２５を再び開始することを試みる。これは、現行の切断が続行できない時に、選定されたグラフにおける新しい位置で切断アルゴリズムを再始動することになる。ステップ４７０が続行できなければ、方法３２５は完了し、次の選定された頂点はまったく存在しない。ステップ３７０で候補頂点が残っている場合、ステップ３８０が、ただ１つだけの候補頂点が残っているためにアルゴリズムが完了したのかどうかを確認するために使用される。複数の候補頂点が残っている場合、ステップ３９０は、候補集合において最大の重み（最も頻繁な使用）を持たない全部の頂点を候補集合から削除する。ステップ４００は、ステップ３７０と同様、全部の候補頂点が削除された場合に方法３２５に再始動を試みさせる。ステップ４１０は、ステップ３８０と同様、単一の候補頂点が見つからなかった場合に方法３２５を終了に移させる。複数の候補頂点が残っているとすれば、ステップ４２０は、候補集合において最大数未満の辺を備える全部の候補頂点を候補集合から削除する。ステップ４２０は、最大数の辺をグラフから削除する候補頂点が選定されることを保証する。ステップ４３０は、ステップ３７０および４００と同様、全部の候補頂点が削除されたという可能性を処理する。同様に、ステップ４４０は、ステップ３８０および４１０と同様、単一の頂点が突き止められたという可能性を処理する。複数の候補頂点が残っているとすれば、ステップ４５０は候補頂点から単一の頂点を任意に選定させる。ステップ４６０は、単一の残りの候補頂点が新しい選定された頂点／資源要求／変数になるように促す。
【００３０】
方法２５０、２６０、２９０および３２５を例証するために、以下の事例を検討する。９つの異なる一意の資源要求／変数｛要求０，要求１，要求２，要求３，要求４，要求５，要求６，要求７，要求８｝および７つの文脈｛文脈Ａ，文脈Ｂ，文脈Ｃ，文脈Ｄ，文脈Ｅ，文脈Ｆ，文脈Ｇ｝が存在すると仮定する。さらに、文脈に含まれている資源要求／変数は次の通りであると仮定する。
【００３１】
【表１】
2004220583.tif 000003
【００３２】
図１２は、ステップ２５４によって上記の表を処理することから結果として得られるグラフ３１０を図示している。
【００３３】
第１の資源／レジスタ対の適用は、以下の通り行われる（若干のステップは省略した）。
１．ステップ２６２：選定された資源／レジスタ対は｛Ｒ０，Ｒ１｝である。
２．ステップ２６６：選定されたグラフは３１０である。
３．ステップ２９２：資源／レジスタ対から選定された資源／レジスタはＲ０である。
４．ステップ３５０：候補頂点集合は｛要求０（２），要求１（１），要求２（２），要求３（３），要求４（２），要求５（２），要求６（３），要求７（２），要求８（２）｝である。
５．ステップ３６０：候補頂点集合は不変である。
６．ステップ３９０：候補頂点の最大の重みは３である。候補頂点集合は｛要求３（３），要求６（３）｝である。
７．ステップ４２０：候補頂点の辺の最大数は５である。候補頂点集合は｛要求６（３）｝である。
８．ステップ４６０：要求６（３）は新しい選定された頂点である。
９．ステップ２９８：要求６（３）は選定された資源／レジスタＲ０を割当てられる。
１０．ステップ３００：選定された資源／レジスタはＲ１である。
１１．ステップ３４０：候補頂点集合は｛要求０（２），要求２（２），要求４（２），要求５（２），要求７（２）｝である。
１２．ステップ３６０：候補頂点集合は不変である。
１３．ステップ３９０：候補頂点の最大の重みは３である。候補頂点集合は不変である。
１４．ステップ４２０：候補頂点の辺の最大数は４である。候補頂点集合は｛要求０（２），要求２（２），要求４（２）｝である。
１５．ステップ４５０：候補頂点集合は任意に｛要求２（２）｝に設定される。
１６．ステップ４６０：要求２（２）は新しい選定された頂点である。
１７．ステップ２９８：要求２（２）は選定された資源／レジスタＲ１を割当てられる。
１８．ステップ３００：選定された資源／レジスタはＲ０である。
１９．ステップ３４０：候補頂点集合は、｛要求０（２），要求３（３），要求４（２）｝である。
２０．ステップ３６０：要求６（３）はＲ０が割当てられている。従って、要求０（２）および要求４（２）はＲ０を割当てることができない。候補頂点集合は｛要求３（３）｝である。
２１．ステップ４６０：要求３（３）は新しい選定された頂点である。
２２．ステップ２９８：要求３（３）は選定された資源／レジスタＲ０を割当てられる。
２３．ステップ３００：選定された資源／レジスタはＲ１である。
２４．ステップ３４０：候補頂点集合は｛要求７（２），要求８（２）｝である。
２５．ステップ３６０：候補頂点集合は不変である。
２６．ステップ３９０：候補頂点の最大の重みは２である。候補頂点集合は不変である。
２７．ステップ４２０：候補頂点の辺の最大数は４である。候補頂点集合は｛要求７（２）｝である。
２８．ステップ４６０：要求７（２）は新しい選定された頂点である。
２９．ステップ２９８：要求７（２）は選定された資源／レジスタＲ１を割当てられる。
３０．ステップ３００：選定された資源／レジスタはＲ０である。
３１．ステップ３４０：候補頂点集合は｛要求５（２），要求８（２）｝である。
３２．ステップ３６０：要求３（３）はＲ０が割当てられている。従って、要求８（２）はＲ０を割当てることができない。要求６（３）はＲ０が割当てられている。従って、要求５（２）はＲ０を割当てることができない。候補頂点集合は空である。
３３．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は｛要求０（２），要求１（１），要求４（２），要求５（２），要求８（２）｝である。
３４．ステップ３６０：要求３（３）はＲ０が割当てられている。従って、要求８（２）はＲ０を割当てることができない。要求６（３）はＲ０が割当てられている。従って、要求０（２）、要求４（２）および要求５（２）はＲ０を割当てることができない。候補頂点集合は｛要求１（１）｝である。
３５．ステップ４６０：要求１（１）は新しい選定された頂点である。
３６．ステップ２９８：要求１（１）は選定された資源／レジスタＲ０を割当てられる。
３７．ステップ３００：選定された資源／レジスタはＲ１である。
３８．ステップ３４０：候補頂点集合は｛要求０（２）｝である。
３９．ステップ３６０：要求２（２）はＲ１が割当てられている。従って、要求０（２）はＲ１を割当てることができない。候補頂点集合は空である。
４０．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は｛要求０（２），要求４（２），要求５（２），要求８（２）｝である。
４１．ステップ３６０：要求２（２）はＲ１が割当てられている。従って、要求０（２）および要求４（２）はＲ１を割当てることができない。要求７（２）はＲ１が割当てられている。従って、要求５（２）および要求８（２）はＲ１を割当てることができない。候補頂点集合は空である。次の頂点はまったく存在しない。
４２．ステップ３０２：両方の選定された資源／レジスタは試されていなかった。選定された資源／レジスタはＲ０である。
４３．ステップ３４０：候補頂点集合は｛要求０（２）｝である。
４４．ステップ３６０：要求６（３）はＲ０が割当てられている。従って、要求０（２）はＲ０を割当てることができない。候補頂点集合は空である。
４５．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は｛要求０（２），要求４（２），要求５（２），要求８（２）｝である。
４６．ステップ３６０：要求６（３）はＲ０が割当てられている。従って、要求０（２）、要求４（２）および要求５（２）はＲ０を割当てることができない。要求３（３）はＲ０が割当てられている。従って、要求８（２）はＲ０を割当てることができない。候補頂点集合は空である。次の頂点はまったく存在しない。
４７．ステップ３０２：両方の資源／レジスタ値が試されたが、次の頂点は見つからなかった。この資源／レジスタ対はこのグラフについて検討し尽くされた。
４８．ステップ２７０：要求１（１）、要求２（２）、要求３（３）、要求６（３）および要求７（２）は、グラフ３１０から除去される。グラフ３１０は依然として単一のグラフとして扱われる。
４９．ステップ２７２：唯一可能なグラフはグラフ３１０であったが、資源／レジスタ対｛Ｒ０，Ｒ１｝を割当てるための次のグラフはまったく存在しない。
５０．ステップ２７４：グラフ３１０は、この時点でそれが複数のグラフであるかどうかを判定するために調べられる。グラフ３２０および３２２が見つかる。
５１．ステップ２６２：選定された資源／レジスタ対は｛Ｒ２，Ｒ３｝である。
５２．ステップ２６６：選定されたグラフは３２０である。
５３．ステップ２９２：選定された資源／レジスタはＲ２である。
５４．ステップ３５０：候補頂点集合は｛要求０（２），要求４（２），要求５（２）｝である。
５５．ステップ３６０：候補頂点集合は不変である。
５６．ステップ３９０：候補頂点の最大の重みは２である。候補頂点集合は不変である。
５７．ステップ４２０：候補頂点の辺の最大数は２である。候補頂点集合は｛要求４（２）｝である。
５８．ステップ４６０：要求４（２）は新しい選定された頂点である。
５９．ステップ２９８：要求４（２）は選定された資源／レジスタＲ２を割当てられる。
６０．ステップ３００：選定された資源／レジスタはＲ３である。
６１．ステップ３４０：候補頂点集合は｛要求０（２），要求５（２）｝である。
６２．ステップ３６０：候補頂点集合は不変である。
６３．ステップ３９０：候補頂点の最大の重みは２である。候補頂点集合は不変である。
６４．ステップ４２０：候補頂点の辺の最大数は１である。候補頂点集合は不変である。
６５．ステップ４５０：候補頂点集合は任意に｛要求０（２）｝に設定される。
６６．ステップ４６０：要求０（２）は新しい選定された頂点である。
６７．ステップ２９８：要求０（２）は選定された資源／レジスタＲ３を割当てられる。
６８．ステップ３００：選定された資源／レジスタはＲ２である。
６９．ステップ３４０：候補頂点集合は空である。
７０．ステップ３６０：候補頂点集合は不変である。
７１．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は｛要求５（２）｝である。
７２．ステップ３６０：要求４（２）はＲ２が割当てられている。要求５（２）はＲ２を割当てることができない。候補頂点集合は空である。
７３．ステップ３０２：両方の選定された資源／レジスタは試されていなかった。選定された資源／レジスタはＲ３である。
７４．ステップ３４０：候補頂点集合は空である。
７５．ステップ３６０：候補頂点集合は不変である。
７６．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は｛要求５（２）｝である。
７７．ステップ３６０：候補頂点集合は不変である。
７８．ステップ４６０：要求５（２）は新しい選定された頂点である。
７９．ステップ２９８：要求５（２）は選定された資源／レジスタＲ３を割当てられる。
８０．ステップ３００：選定された資源／レジスタはＲ２である。
８１．ステップ３４０：候補頂点集合は空である。
８２．ステップ３６０：候補頂点集合は不変である。
８３．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は空である。
８４．ステップ３６０：候補頂点集合は不変である。候補頂点はまったく存在しない。
８５．ステップ３０２：両方の選定された資源／レジスタは試されていなかった。選定された資源／レジスタは、Ｒ３である。
８６．ステップ３４０：候補頂点集合は空である。
８７．ステップ３６０：候補頂点集合は不変である。
８８．ステップ３５０：候補ステップは選定されたグラフにおける全部の未割当ての頂点のうちから本来設定されなかった。候補集合は空である。
８９．ステップ３６０：候補頂点集合は不変である。候補頂点はまったく存在しない。
９０．ステップ３０２：両方の資源／レジスタ値が試されたが、次の頂点は見つからなかった。この資源／レジスタ対はこのグラフについて検討し尽くされた。
９１．ステップ２７０：要求０（２）、要求４（２）および要求５（２）はグラフ３２０から除去される。グラフ３２０は依然として単一のグラフとして扱われる。
９２．ステップ２７２：未処理のグラフ３２２が選定されたグラフになる。
９３．ステップ２６８：要求８（２）は資源／レジスタＲ２を割当てられる。
９４．ステップ２７０：要求８（２）はグラフ３２２から除去される。グラフ３２２は依然として単一のグラフとして扱われる。
９５．ステップ２７４：これ以上分離グラフは存在しなかった。グラフ３２０および３２２の残りがいずれかの残りのグラフを見つけるために調べられる。何も存在しない。全部の資源要求／変数は、資源に割当てられた。
【００３４】
このようにして、方法２５０、２６０、２９０および３２５を用いて、最もアクティブな資源に基づいて資源は資源要求に自動的に割当てられる。最もアクティブな資源要求への資源のこの割当ては、プログラマが資源を手作業で割当てるために一般に使用する方法を模倣している。その結果、方法２５０、２６０、２９０および３２５は、プログラマに理解できる形で資源を割当てる。さらに、資源割当てが失敗した場合、残りの資源要求は、それほど頻繁には使用されないようなものである。さらに、資源割当てが失敗した時には、プログラマは、資源割当てが失敗した時点を指摘され、資源を解放する機会が与えられる。それぞれの使用に基づいて資源が割当てられるので、資源割当てが失敗した時も、プログラマは、相対的にまれに使用される資源を解放するだけである。
【００３５】
アセンブラを用いて資源を大域的に割当てるための方法およびシステムが開示された。本発明に従って書かれたソフトウェアは、メモリ、ＣＤ−ＲＯＭといったいずれかの形態のコンピュータ可読媒体に記憶されるかまたはネットワークによって伝送され、そしてプロセッサによって実行されるはずである。従って、コンピュータ可読媒体は、例えばネットワークによって伝送され得るコンピュータ可読信号を含むものと意図される。本発明は図示した実施形態に従って説明したが、当業者は、それらの実施形態の変種が存在し得て、それらの変種も本発明の精神および範囲内にあるはずであることを容易に認識するであろう。従って、添付物の精神および範囲を逸脱することなく多くの修正が当業者によって行い得る。
【図面の簡単な説明】
【００３６】
【図１】従来のアセンブラの略図である。
【図２】従来のアセンブラを用いて資源を割当てる従来の方法を図示している流れ図である。
【図３】資源を自動的に割当てることができる本発明に従ったアセンブラの１実施形態を図示しているブロック図である。
【図４】本発明に従ってアセンブラを用いて資源を割当てる方法の１実施形態を図示している流れ図である。
【図５】資源割当てが実行されるはずの例示的なコードの一部である。
【図６】資源を自動的に割当てることができるアセンブラに従来のアセンブラを変換する際に使用される修正を付与する方法の１実施形態の流れ図である。
【図７】アセンブラにおいて資源を自動的に割当てるための本発明に従った方法の１実施形態の高水準流れ図である。
【図８】アセンブラを用いて資源を割当てるための本発明に従った方法の好ましい実施形態のより詳細な流れ図である。
【図９】単一のグラフにおいて単一の１対の資源を割当てるための本発明に従った方法の１実施形態を図示している流れ図である。
【図１０】単一のグラフにおける割当てのために単一の頂点を識別するための本発明に従った方法の１実施形態の流れ図を図示している。
【図１１】単一のグラフにおける割当てのために単一の頂点を識別するための本発明に従った方法の１実施形態の流れ図を図示している。
【図１２】本発明に従って資源要求への資源要求の例示的割当てから生じるグラフを図示している。
【図１３】本発明に従って資源要求への資源要求の例示的割当てから生じるグラフを図示している。
【符号の説明】
【００３７】
１０  アセンブラ
１２  パーサ／レクサ
１４  コードジェネレータ
１００  アセンブラ
１０２  レクサ
１０２  パーサ／レクサ
１０４  コードジェネレータ
１０６  資源マネージャ
【図１】
2004220583.tif 000004
【図２】
2004220583.tif 000005
【図３】
2004220583.tif 000006
【図４】
2004220583.tif 000007
【図５】
2004220583.tif 000008
【図６】
2004220583.tif 000009
【図７】
2004220583.tif 000010
【図８】
2004220583.tif 000011
【図９】
2004220583.tif 000012
【図１０】
2004220583.tif 000013
【図１１】
2004220583.tif 000014
【図１２】
2004220583.tif 000015
【図１３】
2004220583.tif 000016