(57)【特許請求の範囲】
【請求項１】
第１のビット幅の２進整数を含む少なくとも１つのソースのオペランドに対するソースの演算を、該第１のビット幅よりも大きい第２のビット幅の２進整数に対して整数演算を実行するプロセッサによって計算するために対応するターゲットの演算に翻訳する方法であって、該方法が、
該ソースの演算を少なくとも１つのターゲットのオペランドを有するターゲットの演算に変換するステップと、
該ターゲットのオペランドの未使用ビットの値が該ターゲットの演算の値に影響を与えるかどうか、および、該ターゲットのオペランドのいずれかが、不適切な値を持つ１つ以上の未使用ビットを有してもよいかどうかを判定するステップと、
該判定ステップの結果が真であった場合に、該ターゲットの演算に対して補正演算を加えて、これにより、該ターゲットの演算を実行する前に、不適切な値を持つ該１つ以上のビットのそれぞれの値を補正するステップと、
を包含する、方法。
【請求項２】
前記少なくとも１つのソースのオペランドが、少なくとも１つの定数を含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのソースのオペランドが、少なくとも１つの変数を含む、請求項１に記載の方法。
【請求項４】
前記少なくとも１つのソースのオペランドが、少なくとも１つのサブ演算を含む、請求項１に記載の方法。
【請求項５】
前記ソースの演算が、算術演算を含む、請求項１に記載の方法。
【請求項６】
前記判定ステップが、符号なし非マスクターゲットのオペランドを特定するステップを包含し、前記補正ステップが、マスクステップを包含する、請求項５に記載の方法。
【請求項７】
前記第１のビット幅がｗビットであり、前記マスクステップが、前記符号なし非マスクターゲットのオペランドと（２w−１）の２進数表現とに対してビット単位ＡＮＤ演算を実行するステップを包含する、請求項６に記載の方法。
【請求項８】
前記判定ステップが、符号付き非符号拡張ターゲットのオペランドを特定するステップを包含し、前記補正ステップが、符号拡張ステップを包含する、請求項５に記載の方法。
【請求項９】
前記ソースの演算が関係演算を含み、前記補正ステップが単調演算を含む、請求項１に記載の方法。
【請求項１０】
請求項１に記載の方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読出し可能な記憶媒体。
【請求項１１】
請求項１に記載の方法を実行するためのプログラムがプログラムされたコンピュータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ソースの演算をターゲットの演算に翻訳する方法に関する。本方法を用いれば、例えば、目標マシン（コンピュータ等）固有の整数ビット幅の倍数ではないビット幅を持つ整数値を効率的に計算することができる。本方法の別の用途としては、高級ハードウェア記述言語のシミュレーションが挙げられる。さらに、本発明は、同方法を実行するコンピュータプログラム、同プログラムを記憶した記憶媒体、同プログラムによってプログラムされたコンピュータ、および同方法によって生成された翻訳生成物にも関する。
【０００２】
【従来の技術】
ＶＨＤＬ（ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，  ＩＥＥＥ  Ｓｔａｎｄａｒｄ  ＶＨＤＬ  Ｌａｎｇｕａｇｅ  Ｒｅｆｅｒｅｎｃｅ  Ｍａｎｕａｌ，  Ｎｅｗ  Ｙｏｒｋ，  ＵＳＡ，  １９９４年６月，  ＩＥＥＥ  Ｓｔｄ  １０７６  １９９３）や、Ｖｅｒｉｌｏｇ  ＨＤＬ（ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，  ＩＥＥＥ  Ｓｔａｎｄａｒｄ  Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ  Ｂａｓｅｄ  ｏｎ  ｔｈｅ  Ｖｅｒｉｌｏｇ  Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ，  Ｎｅｗ  Ｙｏｒｋ，  ＵＳＡ，  １９９６年，  ＩＥＥＥ  Ｓｔｄ  １３６４  １９９５年）のようなハードウェア記述言語を用いて、ハードウェア回路の挙動を記述することができる。これらの言語は、適切な数値型および演算子を提供することによって、整数算術演算を伴う回路の記述をサポートしている。ハードウェアを効率的に設計するために、通常各数値型は、その型の整数値のビット幅をパラメータに有している。
【０００３】
例えば、ＩＥＥＥ  １０７６．３  ＮＵＭＥＲＩＣ＿ＳＴＤ  ＶＨＤＬ  ライブラリ（ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ．  ＩＥＥＥ  Ｓｔａｎｄａｒｄ  Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ  Ｂａｓｅｄ  ｏｎ  ｔｈｅ  Ｖｅｒｉｌｏｇ  Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ，  Ｎｅｗ  Ｙｏｒｋ，  ＵＳＡ，  １９９６年．ＩＥＥＥ  Ｓｔｄ  １３６４  １９９５年）では、ビットベクトルＳＴＤ＿ＬＯＧＩＣ  ＶＥＣＴＯＲの型に基づくＵＮＳＩＧＮＥＤ（符号なし）およびＳＩＧＮＥＤ（符号付き）整数型が規定されている。ビットベクトルは、０値、１値、および、その他の状態（「Ｕ（無限）」、「Ｚ（高インピーダンス）」等）を含むビット値の固定長リストである。ビットベクトルの長さ（および、その数値型の長さ）は固定であるが、ハードウェア設計においては、（それぞれ長さの異なる）いくつかの型のビットベクトルを用いることが可能である。ＶＨＤＬ数値型の個々のビットは０および１以外の値を持ち得るので、ある数値型が持つ値のいくつかは有効な整数に対応しないことに留意されたい。
【０００４】
Ｂａｃｈ言語（Ａｋｉｈｉｓａ  Ｙａｍａｄａ，  Ｋｏｉｃｈｉ  Ｎｉｓｈｉｄａ，  Ｒｙｏｊｉ  Ｓａｋｕｒａｉ，  Ａｎｄｒｅｗ  Ｋａｙ，  Ｔｏｓｈｉｏ  ＮｏｍｕｒａおよびＴａｋａｓｈｉ  Ｋａｍｂｅ，  Ｈａｒｄｗａｒｅ  ｓｙｎｔｈｅｓｉｓ  ｗｉｔｈ  ｔｈｅ  ＢＡＣＨ  ｓｙｓｔｅｍ，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ，  １９９９，  ＧＢ２  ３１７  ２４５）のような高級ハードウェア記述言語を用いれば、Ｃ言語（Ｂｒｉａｎ  Ｗ．  ＫｅｒｎｉｈａｎおよびＤｅｎｎｉｓ  Ｍ．  Ｒｉｔｃｈｉｅ，  Ｔｈｅ  Ｃ  ＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅ，  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  ＵＳＡ，  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，  １９８８）のようなプログラミング言語で通常使用される抽象概念のレベルでハードウェアを記述することができる。
【０００５】
【発明が解決しようとする課題】
Ｃ言語、および一般的なプログラミング言語は、複数種のアーキテクチャをプログラムするために使用されることを想定して設計されるので、その整数型および式のセマンティックスは通常、プログラムを実行する目標アーキテクチャに左右される。例えば、Ｃ言語（Ｂｒｉａｎ  Ｗ．  ＫｅｒｎｉｈａｎおよびＤｅｎｎｉｓ  Ｍ．  Ｒｉｔｃｈｉｅ，  Ｔｈｅ  Ｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ，  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  ＵＳＡ，  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，  １９８８）は、ｉｎｔおよびｕｎｓｉｇｎｅｄ  ｉｎｔ型を供給するが、これらはそれぞれ、目標マシンに固有のビット幅を与えられた符号付きおよび符号なし整数に対応する。Ｃ言語の整数型は柔軟性に乏しいのでハードウェアの効率的な設計にＣ言語は向かない。そこで、Ｂａｃｈハードウェア記述言語は、符号付きおよび符号なしｗビットの整数を表すｉｎｔｗおよびｕｎｓｉｇｎｅｄ  ｉｎｔｗのような固定幅の整数型によってＣ言語を拡張している。
【０００６】
ＶＨＤＬのような低級のものよりもＢａｃｈのようなプログラム言語系の高級ハードウェア記述言語を使用することの利点の１つは、格段により高速に設計の挙動を（汎用アーキテクチャ上で）シミュレーションできることである。例えば、上記のＶＨＤＬ数値型の特定の抽象レベルのために、シミュレーションに使用される目標マシンの整数算術演算を直接には使用できない。一般に、数値型の各ビット値を目標マシン上の独立したバイト／ワードとして表現する必要があり、そこでＶＨＤＬ算術演算シミュレーションは、目標マシンの固有の算術演算よりもはるかに遅くなり得る。Ｂａｃｈの算術演算は、ＶＨＤＬ数値算術演算よりも目標マシンの固有の算術演算に近いが、それでもビット幅の違いのために目標マシンの固有の算術演算をそのままでは使用できない。したがって、ハードウェア記述に通常使用される算術演算の固定幅を正確にかつ効率的にシミュレーションするための方法を開発する必要がある。
【０００７】
Ｖａｌｅｎ−Ｃコンパイラ（Ｇｒａｄｕａｔｅ  Ｓｃｈｏｏｌ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｅｌｅｃｔｒｉｃａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ  （Ｋｙｕｓｈｕ  Ｕｎｉｖｅｒｓｉｔｙ）、ＡｄｖａｎｃｅｄＳｏｆｔｗａｒｅ  Ｔｅｃｈｎｏｌｏｇｙ  ａｎｄ  Ｍｅｃｈａｔｒｏｎｉｃｓ  Ｒｅｓｅａｒｃｈ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｋｙｏｔｏ、  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｉｅｓ  （Ｋｙｕｓｈｕ）、およびＭｉｔｓｕｂｉｓｈｉ  Ｅｌｅｃｔｒｉｃ  Ｃｏｒｐｏｒａｔｉｏｎ．Ｖａｌｅｎ−Ｃ  Ｃｏｍｐｌｉｅｒ  Ｄｅｖｅｌｏｐｍｅｎｔ  Ｄｏｃｕｍｅｎｔ  （英語版１．０１）．Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ  ｐｒｏｍｏｔｉｏｎ  Ａｇｅｎｃｙ、日本、１９９８年４月）のようなリターゲタブル可能コンパイラを使用すれば、入力ソースプログラムを異なる目標マシンのアセンブリ／機械語にコンパイルすることができる。Ｖａｌｅｎ−Ｃコンパイラの入力言語は、ＡＮＳＩ  Ｃ言語をやはり固定幅整数型によって拡張したＶａｌｅｎ−Ｃプログラミング言語である。プログラマは、ｉｎｔｗという語の整数型を特定することができる。ここでｗは、その型の幅を表す任意のゼロでない自然数である。しかし、Ｖａｌｅｎ−Ｃ整数算術演算のセマンティックスは、やはり目標アーキテクチャに依存し、整数型ｉｎｔｗは実際には、少なくともｗビット長であるとして定義され、その幅は目標マシンのワードサイズの倍数である。その結果、コンパイルされたコードの挙動は、目標マシンが変ると異なる。
【０００８】
Ｄｅ  Ｃｏｓｔｅｒら、「Ｃｏｄｅ  ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  ｃｏｍｐｉｌｅｄ  ｂｉｔ−ｔｉｍｅ  ｓｉｍｕｌａｔｉｏｎ  ｏｆ  ＤＳＰ  ａｐｐｌｉｃａｔｉｏｎｓ」、１１th  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｙｓｔｅｍ  Ｓｙｎｔｈｅｓｉｓ  （ＩＳＳＳ  ’９８）１９９８年１２月２〜４日、Ｈｓｉｎｃｈ、Ｔａｉｗａｎ（ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｐｕｂｌｉｃａｔｉｏｎｓ）、９〜１４頁は、デジタル信号処理（ＤＳＰ）アプリケーションの効率的なシミュレーションのために固定小数点整数算術演算を標準的な整数算術演算に翻訳するための方法を開示する。しかし、得られた整数算術演算式における値補正演算を最小限にする努力は行われておらず、目標マシンのリソースが効率的に使用されていない。
【０００９】
欧州特許０  ６２６  ６４０および欧州特許０  ６２６  ６４１は、高級処理言語を機械語に変換するための技術を開示する。これらの技術は、プログラムがコンピュータによって実行される場合に、ユーザが介入して演算の値がオーバーフローする恐れがないかどうかを計算する必要がある。オーバーフローしそうであれば、値補正演算を行う。その値補正演算は、マスキング演算、もしくは演算が符号なしかまたは符号付きかのいずれであるかに依存する符号拡張演算を含む。
【００１０】
【課題を解決するための手段】
本発明の第１の局面によると、第１のビット幅の２進整数を含む少なくとも１つのソースのオペランドに対するソースの演算を、上記第１のビット幅よりも大きい第２のビット幅の２進整数に対して整数演算を実行するプロセッサによって計算するために対応するターゲットの演算に翻訳する方法であって、上記ソースの演算を少なくとも１つのターゲットのオペランドを有するターゲットの演算に翻訳するステップと、上記ターゲットのオペランドの未使用ビットの値が上記ターゲットの演算の値に影響を与えるかどうか、および、上記ターゲットのオペランドのいずれかが、不適切な値を持つ１つ以上の未使用ビットを有してもよいかどうかを判定するステップと、上記判定ステップの結果が真であった場合に、上記ターゲットの演算に対して補正演算を加えて、これにより、上記ターゲットの演算を実行する前に、不適切な値を持つ該１つ以上のビットのそれぞれの値を補正するステップと、を包含する方法が提供される。
【００１１】
上記少なくとも１つのソースのオペランドは、少なくとも１つの定数を含んでもよい。
【００１２】
上記少なくとも１つのソースのオペランドは、少なくとも１つの変数を含んでもよい。
【００１３】
上記少なくとも１つのソースのオペランドは、少なくとも１つのサブ演算を含んでもよい。
【００１４】
上記ソースの演算は、算術演算を含んでもよい。上記判定ステップは、符号なし非マスクターゲットのオペランドを特定するステップを包含し、上記補正ステップは、マスクステップを含んでもよい。上記第１のビット幅はｗビットであってもよく、上記マスクステップは、上記符号なし非マスクターゲットのオペランドと（２w−１）の２進数表現とに対してビット単位ＡＮＤ演算を実行するステップを含んでもよい。上記判定ステップは、符号付き非符号拡張ターゲットのオペランドを特定するステップを含んでもよく、上記補正ステップは、符号拡張ステップを含んでもよい。
【００１５】
上記ソースの演算は関係演算を含んでもよく、上記補正ステップは単調演算を含んでもよい。
【００１７】
本発明の第３の局面によると、本発明の第１の局面による方法を実行させるためのコンピュータプログラムを記憶した記憶媒体が提供される。
【００１８】
本発明の第４の局面によると、本発明の第１の局面による方法を実行するためのプログラムがプログラムされたコンピュータが提供される。
【００２０】
ターゲットのオペランドの用語「未使用ビット」は、ターゲットのオペランドのうちのビットであって、対応するソースの演算の値を表すために使用されていないビットを意味する。
【００２１】
未使用ビットの用語「不適切な値」は、未使用ビットの値であって、その未使用ビットがターゲットのオペランドに存在する場合に、対応のソースの演算の値と異なる値に計算されるターゲットの演算を生じるような値である。
【００２２】
このように、所定のビット幅の整数算術演算式を計算する能力があるだけの所定のデバイスを使用して、算術演算および任意のビット幅の整数を伴う関係式の効率的な計算を行う方法を提供することができる。
【００２３】
いくつかの特定の幅（例えば、ｗ1、ｗ2など）の整数算術演算を計算することのできる、目標マシンと呼ばれる所定のデバイスまたは機構に対して、上記の方法は、任意の幅の整数を伴う算術演算式を特定の幅の整数を伴う効率的な算術演算に翻訳する。任意の幅の整数算術演算を伴う式の言語は、ソース言語と称す。同様に、特定の幅（例えば、ｗ1、ｗ2など）の整数算術演算を伴う式の言語は、目標言語と称す。この方法を使用して：
・幅ｗを有する整数原子式（定数または変数など）は、少なくともｗビット幅である最短幅の目標言語整数の幅を有する原子式によって表される。例えば、幅５の符号なし原子式は、目標言語が幅１６、３２、４８などの整数を含む場合に幅１６の原子式によって表される。
【００２４】
２０(U5)→２０(U16)
・表記ｘ(Uw)は、その式が幅ｗの符号なし整数型を有することを表し、ｘ→ｙは、ソース式ｘが目標式ｙに翻訳されることを表す。
【００２５】
・目標言語における算術演算は、可能な限りいつでも使用される。例えば：
ａ(U5)＋ｂ(U5)→ａ(U16)＋ｂ(U16)
・ソース言語および目標言語における幅が異なるので、ターゲットの演算の値は、ソース言語における値と異なることがある：
２０(U5)＋３０(U5)＝１８(U5)、他方２０(U16)＋３０(U16)＝５０(U16)
そこで、目標式における演算の値が必要な場合に確実にソース式における演算の値と同じにするために値補正演算が必要になることがある：
ａ(U5)＋ｂ(U5)→（ａ(U16)＋ｂ(U16)）＆３１(U16)
ここで＆は、ビット単位ＡＮＤ演算子である。演算ｘ(U16)＆３１(U16)は、式ｘ(U16)に含まれた１６ビット値を補正する。ここでｘ(U16)＆３１(U16)は、５ビット符号なし値を表すと仮定する。
【００２６】
値補正演算は、翻訳されるどのサブ式に対しても適用されるわけではなく、そのような演算が必要な場合に適用される。例えば、式：
（（ａ(U5)＋ｂ(U5)）＊ｃ(U5)）／（ｄ(U5)＋ｅ(U5)）
はそのまま、以下の式に翻訳されるのではなく：
（（（（ａ(U16)＋ｂ(U16)）＆３１(U16)）＊ｃ(U16)）＆３１(U16)）／（（ｄ(U16)＋ｅ(U16)）＆３１(U16)）＆３１(U16)）
ここでは、８回の目標マシン演算が使用されるが、さらに効率を上げるには以下の式に翻訳される：
（（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）＆３１(U16)）／（（ｄ(U16)＋ｅ(U16)）＆３１(U16)）
ここでは、６回の演算が使用される。
【００２７】
・これは、目標式（ソース式表現を目標マシン表現に翻訳するために使用されるマシン上のメモリローケーション、またはレジスタ）の内部表現を使用して達成される。この目標式は、以下を含む：
１．目標マシン式の表現；
２．以下のさらなる情報を伴う：式の符号、元の式の幅（有効幅と呼ぶ）、目標式の幅（表現幅と呼ぶ）、およびソース式の値を記憶するために使用されない目標式の整数値におけるビットの可能な値についての情報（上位ビット特性と呼ぶ）。ソース式の値を記憶するために使用されない目標式の値におけるビットを未使用ビットと呼ぶ。
【００２８】
この情報は、追加タイプ情報と呼ぶ。特に重要なのが、上位ビット特性情報であり、これは、以下の２つの特性が満足されるかどうかを示す：
・未使用ビットのすべてが０であることを示すマスク特性。
【００２９】
・未使用ビットのすべてがソース式の値の最上位ビットと同じであることを示す符号拡張特性。
【００３０】
これら２つの特性は以下の理由により重要である、
・式が符号なしの場合、ソース式の値は、目標式がマスク特性を有する場合かつその場合に限り、その目標式の値と同じである。
【００３１】
・式が符号付きの場合、ソース式の値は、目標式が符号拡張特性を有する場合かつその場合に限り、その目標式の値と同じである。
【００３２】
さらなるメモリローケーションを使用して追加タイプ情報を記憶することによって（目標マシン式の表現を記憶するために必要なメモリローケーションとは別）、上記のような翻訳方法は、以下の場合にのみ、目標式中に適切な値補正演算を挿入することができる：
１．目標式の値が、ソース式の値と異なる（すなわち、式が符号なしであり、かつマスク特性を有さない場合か、または式が符号付きであり、かつ符号拡張特性を有さない場合）、および
２．翻訳される演算が、そのオペランドの正しい目標式値を必要とする。＋および＊のような所定の演算は、有効ビットにおける値がソース式のビットにおける値と同じである限り、ターゲットのオペランドに対する正しい値を必要としない。その結果、それらのオペランドは、目標式を構築する場合に値補正する必要がない。
【００３３】
＼のような他の演算は、そのオペランドに対する正しい値が必要であり、そこでその値は、その適切な上位ビット特性（式が符号なしの場合にマスクされ、そうでなければ符号拡張される）が設定されない場合に値補正される必要がある。
【００３４】
所定の演算（＼など、＋および＊ではない）の結果が正しく、そこで適切な上位ビット特性が目標式の追加タイプ情報中に設定され得るので、得られた式について値補正がその後必要とならない。
【００３５】
値補正演算は、そのまますべての演算に挿入されるわけではないので、得られた目標式はさらに効率的である。
【００３６】
上記のような方法は、任意のビット幅の整数を伴う算術演算がプロセッサまたは所定のビット幅のみの算術演算を効率的に計算できる任意のデバイス上で計算される必要がある場合に使用され得る。このような方法の産業上のアプリケーションは、以下を含む：
・ある特定の目標マシン上の算術演算回路の高級記述（Ｂａｃｈまたは他を使用する）の効率的シミュレーション。ハードウェアがＢａｃｈ高級言語で記述され、そして低級合成可能産業強度ハードウェア記述が自動的に生成される。ハードウェア設計者は、低級言語（ＶＨＤＬなど）の代わりに高級言語を使用するので、従来のハードウェア設計プロセスよりも設計プロセスは格段に速くなり、故に安価となる。本発明は、Ｂａｃｈ設計フローのシミュレーション段階において使用され得る。その段階では、実際のハードウェアが合成される前にＢａｃｈハードウェア記述が確認される。これにより、シミュレーション段階を、元のままの方法を使用する場合よりも格段に速くでき、したがってハードウェア設計にかかる時間を低減できる。
【００３７】
・固有の整数算術演算がシミュレーションで使用されるものと異なるマシンを対象とする算術演算の効率的なシミュレーションまたはコンパイル。例えば、特定のプロセッサ（遅いか、または実施段階の間に容易に得られないようなもの）を対象とするプログラムを、目標マシンアーキテクチャと異なるアーキテクチャを有するより速く、容易に得られるプロセッサ上でシミュレーションできる。
【００３８】
・ハードウェアおよびソフトウェアの両方の効率的なシミュレーションが必要となる埋め込みシステムの設計の効率的なシミュレーション。
【００３９】
容易に得られる利点は、以下を含む：
・上記の方法によって生成された目標式は、目標マシンの固有の整数算術演算が直接使用され、かつ値補正演算の回数が低減するので効率的である。
【００４０】
・翻訳方法それ自体は、時間／空間が高価でなく、したがってソース式の目標式への高速なコンパイルが必要であるアプリケーションにおいても使用できる。
【００４１】
本発明によればソースの演算をターゲットの演算に翻訳する方法を提供する。ソースの演算は、それぞれ第１のビット幅の２進整数を含む１つ以上のソースのオペランドに対して実行される。ターゲットの演算は、第１のビット幅よりも大きな第２のビット幅の２進整数に対して整数演算を実行するコンピュータ等のプロセッサによって計算される必要がある演算である。ソースの演算１は、少なくとも１つのターゲットのオペランドを有するターゲットの演算に翻訳される。ステップ３では、ターゲットのオペランドの未使用ビットの値がターゲットの演算の値に影響を与えるかどうかを判定し、ステップ５では、いずれかのターゲットのオペランドが、不適切な値を持つ１つ以上の未使用ビットを有してもよいかどうかを判定する。ステップ３およびステップ５の判定結果が、いずれも真であった場合、ステップ６において、ターゲットの演算に対して補正演算を加えて、これにより、ターゲットの演算を実行する前に、不適切な値を持つ各ビットの値を補正する。
【００４２】
【発明の実施の形態】
本発明を、添付の図面を参照し、実施例を用いてさらに説明する。
【００４３】
図面全体を通して同様の部分は同様の参照符号で示す。
【００４４】
図１は、ソースの演算をターゲットの演算に翻訳する方法を例示する。ソースの演算は、第１のビット幅の２進整数について実行され、算術演算または関係演算を含むことがある。ターゲットの演算は、第１のビット幅よりも大きい第２のビット幅を有する整数について算術演算および／または論理演算を実行するコンピュータなどのデバイスによって実行される。
【００４５】
ステップ１は、ソースの演算を入力し、ステップ２は、ソースの演算を対応のターゲットの演算に翻訳する。ステップ３は、ターゲットの演算のいずれかの未使用ビットがターゲットの演算に影響を与え得るかどうかを検出する。ここで、ターゲットの演算が「影響」を受けるのは、未使用ビットが存在することによって、ターゲットの演算の計算が対応のソースの演算の計算と異なる結果となる場合である。どの未使用ビットもターゲットの演算に影響を与えなければ、ターゲットの演算は、ステップ４において目標マシンによる後続の処理のために出力される。
【００４６】
未使用ビットがターゲットの演算に影響を与え得る場合、ステップ５は、いずれかのターゲットのオペランドが不適切な未使用ビットを有するかどうかを検出する。例えば、ターゲットのオペランドのオペランドはまた、ターゲットの演算の計算が影響を受けないような値にあらかじめ設定される未使用ビットを有することがある。この場合、制御は、ターゲットの演算を出力するステップ４に遷移する。しかし、ターゲットのオペランドが不適切な未使用ビットを有する場合、ステップ６は、ステップ４でターゲットの演算を出力する前に補正演算をターゲットの演算に加える。したがって、ターゲットの演算が目標マシンについて実行されるならば、得られる計算はソースの演算の計算と同じであることを確実にできる。
【００４７】
図２は、図１に例示される翻訳方法を実行するために使用され得るコンピュータを例示する。コンピュータは、算術かつ論理ユニット１１を含むマイクロプロセッサ１０を含む。マイクロプロセッサは、翻訳のためのソースの演算を受信するための入力インターフェース１２および得られた翻訳生成物をターゲットの演算の形態で供給するための出力インターフェース１３を含んで提供される。コンピュータは、図１に例示する方法を実行するようにマイクロプロセッサ１０を制御するためのプログラムを含む読み取り専用メモリ１４を有する。コンピュータはまた、マイクロプロセッサ１０の演算の間に発生する値を一時的に記憶するためのランダムアクセスメモリ１５を有する。
【００４８】
図１に例示する方法は、本発明の非常に基本的な実施態様である。さらに高度な方法を以下により詳細に説明する。以下の方法は、図１を参照して説明される「演算」に同等な「式」の翻訳を実行する。
【００４９】
算術演算式は値を計算し、値のセットは、以下を含むと考える：
・任意のビット幅の符号なし２進整数；
・任意のビット幅の符号付き２進整数。
【００５０】
符号なし整数に対して標準的な符号なし２進解釈を仮定する。例えば、符号なし２進数１１０１は、整数１３と解釈される；および符号付き整数に対して２の補数解釈を仮定する。例えば、符号付き２進数１１０１は、整数−３と解釈される。
【００５１】
値式の異なる型を区別するために、すべての式が形態に関して型を区別される：
・符号なし整数値に対してｕｎｓｉｇｎｅｄω、または単にＵω；または
・符号付き整数値に対してｓｉｇｎｅｄω、または単にＳω；
ここで幅ωは、値におけるビット数を表すゼロでない正の整数である。通常、ｅ(t)と書いてｅが型ｔを有することを示す。式の型は通常、前後から推定され得る場合、または本論と関係しない場合には省略される。
【００５２】
式は、
定数および変数などの原子であるか、または
多くの式ｅ1、ｅ2、．．．、ｅn（オペランドと呼ぶ）に演算子（例えば、ｏｐ）をかけたものからなる複合物：
ｏｐ（ｅ1、ｅ2、．．．、ｅn）。
【００５３】
定数は、固定値（故にその名がある）に計算され、他方変数の値は、割り当て（変数からその型の値へのマッピング）によって与えられる。複合式の値は、演算子およびそのオペランドの計算に依存する。式の計算は、副作用を有し得る：
すなわち、変数の割り当てを変更し得る。例えば、以下の初期割り当てが与えられ：
ｘ(S16)→１０(S16)
ｙ(S16)→２０(S16)
そして演算子＝、＋、＊についてはＣ言語のセマンティックスを仮定すると、
（ｘ(S16)＝ｘ(S16)＋１，ｙ(S16)＝ｘ(S16)＊ｙ(S16)）
の計算は，値２２０(S16)を返し、割り当てを以下のように変更する：
ｘ(S16)→１１(S16)
ｙ(S16)＝２２０(S16)
その目的は、任意のビット幅の算術演算サブ式を伴う式を、所定のビット幅：ω1、ω2、．．．だけを伴う算術演算式を効率的に計算できる目標マシンを使用して計算できることである。既存の方法（例えば、Ｇｉｌｅｓ  ＢｒａｓｓａｒｄおよびＰａｕｌ  Ｂｒａｔｌｅｙ、Ａｌｇｏｒｉｔｈｍｉｃｓ：Ｔｈｅｏｒｙａｎｄ  Ｐｒａｃｔｉｃｅ、Ｐｒｅｎｔｉｃｅ−ｈａｌｌ、ＵＳＡ、１９９８年を参照）を使用すれば、特定の幅の１つの倍数の幅を有する整数について、目標マシン上で効率的に算術演算を計算できる。これらの方法を使用して、所与の目標マシンが無限数の幅：ω1、ω2、．．．２ω1、２ω2、．．．３ω1、３ω2、．．．などを伴う整数算術演算を効率的に計算できると仮定し得る。これらのビット幅を目標マシンの固有ビット幅と称する。目標マシンによって直接計算され得る式のセットを以下のステートメントによってより形式的に定義される目標言語と称す：式ｅは、ｅのすべてのサブ式の幅が固有ビット幅である場合かつその場合に限り目標言語に含まれる。また、ソース言語を任意の幅を有する式のセットとして定義する。
【００５４】
図３は、所与の目標マシン２１を用いてソース言語の式２０を計算できる方法の概観を与える。この方法の核心は、型補正ソース式２３を受け取り、目標式の内部表現２４を返す翻訳機構２２である。式は、例えば、算術２進演算のオペランドの型がその演算によって返される値の型と同じであるといったような多くの言語依存型ルールに従う場合に、型が正しい。したがって、ソース式は、型適正式にまず型変換されると仮定する。型変換機構は、ソース言語のセマンティックスに依存し、ここでは議論しない（Ｃ言語の式の型変換機構については（Ｂｒｉａｎ  Ｗ．  ＫｅｒｎｉｇｈａｎおよびＤｅｎｎｉｓ  Ｍ．  Ｒｉｔｃｈｉｅ，Ｔｈｅ  Ｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ，  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  ＵＳＡ，  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，  １９８８年）の付録Ａ６を参照）。型適正ソース式が与えられると、翻訳機構２２は、目標マシン読み取り可能式２５が抽出および計算され得る目標式の内部表現２４を返す。目標式の内部表現からマシン読み取り可能式を抽出するための機構は、使用される目標マシンに依存し、ここでは議論しない。
【００５５】
図４は、ソース整数値が目標整数値によってどのように表されるかを例示する。基本的には、ｎビット整数が同じ符号のｍビット目標整数によって表され、ここでｍはｎ以上の最小固有ビット幅である。ソース整数ビット２６は、目標整数の最下位ｎビット２７中に記憶される。目標整数値中の最上位（ｍ−ｎ）ビット２８は、未使用ビットと呼ばれる。目標整数値の最下位ｎビット２７は、有効ビット列と呼ばれる。目標値の解釈がソース値の解釈と同じであるためには：
・ソース整数値が符号なしである場合、目標整数値がマスクされる：目標整数値中の未使用ビットが０に設定される。
【００５６】
・ソース整数値が符号付きである場合、目標整数値が符号拡張される：目標整数値の未使用ビットが、有効ビット列中の最上位ビットに設定される。
【００５７】
目標言語式の内部表現は、図５に例示され、以下を含む：
・目標マシンに依存する目標式の内部表現２９；および
・効率的な目標式を生成するために翻訳プロセスによって使用される型情報３０。
【００５８】
表記＜ｉ＞ｔを使用して、型情報ｉを有する目標式ｔの内部表現を示す。目標式の内部表現は、式の目標マシン読み取り可能表現を返す抽出演算を有するべきである。
【００５９】
型情報３０は、以下の機能を有するデータ構造である：
ｓｉｇｎ：符号付きかまたは符号なしかであり得る式の符号である。
【００６０】
有効幅：目標式の有効幅は、それが表す元の式の幅である。
【００６１】
表現幅：目標式の表現幅は、目標マシン上でのその実際のビット幅である。整数式の表現幅は、その有効幅以上である。式の型は、その表現幅がその有効幅と同じである場合に、正確であるとされる。有効幅よりも上位の不正確な整数表現におけるビットを未使用ビットと呼ぶ。
【００６２】
上位ビット値：不正確な式の上位ビット値または上位ビット特性は、その未使用ビットについての情報を与える。式の上位特性は：
マスク：目標式は、どの割り当てに対しても、未使用ビットがすべて０に設定される値に必ず計算される場合に、マスク特性が与えられる。
【００６３】
符号拡張：目標式は、どの割り当てに対しても、未使用ビットが有効ビット列における最上位ビットと同じ値を有する値に必ず計算される場合に、符号拡張特性を与えられる。
【００６４】
これらの特性は、以下の例に示すように互いに排他的でない。以下の例は、表現幅１６および有効幅９を有する整数値をいくつかリストする。
【００６５】
【表１】
0003755733.tif 000002
目標式は、どの割り当てに対しても、その有効ビット列の解釈と同じ解釈を有する値に計算される場合、忠実であるとされる（同一の符号を仮定）。したがって、式が忠実となるのは以下の場合である：
・符号なしであり、かつマスク特性を有する、または
・符号付きであり、かつ符号拡張特性を有する。
【００６６】
目標式の各サブ式に型情報を用いてさらに注釈をつけるのが都合のよい場合がある、なぜなら：
・式の符号および表現幅が、目標式のマシン読み取り可能表現を抽出する演算によって必要とされ得る；
・有効幅および上位ビット特性を利用する目標式の内部表現について最適化を図り得る。
【００６７】
式の上位ビット値を一般化して、その式のマスキングおよび符号拡張の範囲を以下の２つの値によって与える：
マスキング範囲：目標式ｅは、どの割り当てについてもｎ以上の位置のビットが０である値に必ず計算される場合に、ｎのマスキング範囲を有する。ここで、ｎは、ｅの表現幅よりも小さい。
【００６８】
０００００００１０１０１０００１１は、１０のマスキング範囲を有する。
【００６９】
１１１１１００００００１０１０１０は、１７のマスキング範囲を有する。
【００７０】
符号拡張範囲：目標式ｅは、どの割り当てについてもｎ以上の位置のビットがビットｎ−１に等しい値に必ず計算される場合に、ｎの符号拡張範囲を有する。ここで、ｎは、ｅの表現幅よりも小さく、かつ０より大きい。
【００７１】
０００００００１０１０１０００１１は、１１の符号拡張範囲を有する。
【００７２】
１１１１１００００００１０１０１０は、１３の符号拡張範囲を有する。
【００７３】
なお、従来通り、ビット列の最下位ビットは位置０にある。
【００７４】
整数式の表現は、その式によって計算された値が必要に応じてマスクまたは符号拡張されることを保証する値補正演算を適用することによって、忠実にされ得る。目標式表現についての以下の２つの演算が定義されると仮定する：
マスキング演算は、式ｔを受け取り、式ｔ’を返す。ここで、どの割り当てについてもｔおよびｔ’の有効ビット列が同じであり、かつｔ’がマスク特性を有する。
【００７５】
符号拡張演算は、式ｔを受け取り、式ｔ’を返す。ここで、どの割り当てについてもｔおよびｔ’の有効ビット列が同じであり、かつｔ’が符号拡張特性を有する。
【００７６】
式ｔが与えられたとき、マスキング演算および符号拡張演算に適用された式ｔを表すためにそれぞれ表記ｍ（ｔ）およびｓ（ｔ）を使用する。また、式ｔが与えられたとき、ｔが符号なしの場合にｍ（ｔ）を返し、ｔが符号付きの場合にｓ（ｔ）を返す「忠実化」演算を定義する。
【００７７】
ｍ（ｔ）およびｓ（ｔ）によって表される目標式の計算は、ｔによって表される目標式の計算よりも時間／空間的により高価であることもあり、そこでソース整数式の目標整数式への翻訳は、これらの演算を翻訳されるサブ式のいずれにもそのまま適用するのではなく、これらの演算の適用を最小限にする試みをすべきである。
【００７８】
所定の場合には、値補正演算は、ある特定の式を計算する時間／空間のコストが値補正演算の計算と同じであるように実行される。これは確かに、すでに値補正された式の場合である。なぜなら、演算は単に元の式を返すだけだからである。これは定数式の場合でもある。なぜなら、定数式は、定数値を直接的に補正し、別の定数式（同じコストのもの）を返すことによって値補正されるからである。式ｔは、ｍ（ｔ）の計算がｔの計算と同じコストを有する場合、容易にマスクされる。同様に、式ｔは、ｓ（ｔ）の計算がｔの計算と同じコストを有する場合、容易に符号拡張される。
【００７９】
ブール値（これは、２つの真理値：真および偽についての表現である）を返す副作用のない関係演算子（＜および＜＝など）をともなう整数式を翻訳する場合、オペランドに対して値補正演算を必ずしも行う必要はない。代わりに、以下の特性を満たすオペランドに通常安価な単調演算を行うことで十分である：
・ｏｐS（ｓ1，．．．，ｓn）は、ｏｐT（ｍｎ（ｔ1），．．．，ｍｎ（ｔn））が真を表すブール値を計算する場合かつその場合に限り真を表すブール値を計算する。
【００８０】
・ｏｐS（ｓ1，．．．，ｓn）は、ｏｐT（ｍｎ（ｔ1），．．．，ｍｎ（ｔn））が偽を表すブール値を計算する場合かつその場合に限り偽を表すブール値を計算する。
ここで、ｍｎ（ｔ）は、目標式ｔに適用された単調演算を表し、ｏｐSはソース言語におけるｎ進関係演算、ｏｐTは目標言語における対応のｎ進関係演算、ｓ1，．．．，ｓnはソース式、ｔ1，．．．，ｔnはそれらに対応の（必ずしも値補正されない）目標式である。
【００８１】
異なる関係演算子は、異なる単調演算を必要とすることがある。また、同じ関係演算子に適用可能な単調演算がいくつかあり得る。
【００８２】
ここで、型補正ソース式の目標式の内部表現への変換を説明する。まず、ソース式を目標式に翻訳するための一般的機構を説明し、その後いくつかのＣ言語風の演算子を伴う算術演算式の１セットに対するこの処理を具体的に例示する。
【００８３】
ソース式の目標式への変換は、ソース言語における異なる演算子に依存する。その方法は、ソース言語における演算子の以下の特性を使用する：
特性１は、演算の結果の未使用ビットの値を取り扱う。＋、−、および＊などの所定の演算において、オペランドの未使用ビットは、その結果の有効ビットに影響を与えず、そのようなオペランドのオペランドは、ソース式が目標式に翻訳される場合には、値補正演算に適用されない。オペランドの未使用ビットは、その結果の有効ビットに影響を与え得、そしてこの特定のオペランドは、値補正される必要があるか、または関係演算の場合、すべてのオペランドは、有効な単調演算に適用される必要がある。
【００８４】
特性２は、オペランドの未使用ビットおよび有効ビットが演算の結果の未使用ビットにどのように影響を与えるかを取り扱う。＼および％などの所定の演算において、その結果の値は忠実であることが保証され、そこで適切な上位ビット特性が、目標式の型情報内に設定され得る。
【００８５】
基本的に、ここで説明される方法は、
・式の上位ビット値を含む算術演算または論理式を表す拡張データ構造を使用する。
【００８６】
・必要な場合のみに値補正機能を演算のオペランドに適用する上記２つの特性を考慮する。
【００８７】
これらの点は、本発明の方法が、値補正機能を演算の結果に常に適用する公知の方法と異なることを例示する。
【００８８】
例えば、データ構造を拡張すれば、式のマスキングおよび符号拡張範囲を含むことができ、そしてこれらの特性から、本発明の方法は、翻訳の間に必要とされる値補正機能の数を著しく低減させる。以下においては単に、式のデータ構造内にマスクおよび符号拡張特性を記憶させ、そしてこれら２つの特性が、本発明の方法をどのように効率的に使用して効率的な目標式を生成するのかを説明する。マスクおよび符号拡張特性の代わりにマスキングおよび符号拡張範囲を考慮する場合、本発明の方法は、若干より効率的な式を生成する。例えば、以下の式のサブ式：
（ａ(U5)＆３(U5)）＋１(U5)
は、以下のマスキング範囲を有する：
ａ(U5)＆３(U5)  ２
１(U5)  １
そして、結果のマスキング範囲が１足すオペランドの最大マスキング範囲である＋演算子の特性を使用して、主式のマスキング範囲が１＋２＝３であることを推論する。したがって、主式は、マスクされ、そして忠実であることが分かる。その結果、値補正される必要は決してない。マスキング範囲を追跡するかわりに、マスク特性を単に追跡する場合は、上記２つのサブ式がマスク特性を有することから、主式がまたマスクされるとは推論できない。これが意味するところは、式は、更なるマスキング演算を付加することによって値補正される必要があり得ることである。
【００８９】
幅ωのソース式表現ｅが与えられると、目標式表現は以下のように構築される：
ステップ１  ソース式ｅにおける変数を有する上位ビット特性に関する表が構築される。この表は、上位ビット特性マッピングと呼ばれ、以下の形態を有する：
【００９０】
【表２】
0003755733.tif 000003
ここで、Ｕ0．．．．Ｕnはすべてソース式ｅにおける変数であり、そしてＰ0．．．．Ｐnはそれらに対応する上位ビット特性であり、その上位ビット特性は、以下のうちの１つである：マスク、符号拡張、またはなし（すなわち３つの取り得る値である）。マスクおよび符号拡張特性の両方が設定されるような上位ビット特性の組み合わせは、この表において許されない。いくつかのデータ構造を上位ビット特性マッピングの内部表現のために使用でき、そして変数Ｕ0．．．．Ｕnを並べ替えることができる場合、適切な構造は、連想リストおよびソート２進ツリーを含む。
【００９１】
上位ビット特性マッピングは翻訳機構の正確さに影響せず、例えば、すべての変数に上位ビット特性を全く与えないような自明マッピングを使用することができる。しかし、変数がソース式においてどのように（およびどのくらいの頻度で）使用されるかに依存する上位ビット特性マッピングを構築する発見的方法を開発できる。そのため、この翻訳機構によって構築される目標式は、より効率的となり得る可能性がある。
【００９２】
ステップ２  以下のデータを有する型情報が構築される：
・ソース式と同じ符号；
・有効幅ω；
・表現幅ｒは、ω以上の最小固有幅となるよう選択される；
・上位ビット特性が全く設定されない（現時点で）。
【００９３】
この型情報は、ｉeによって示される。型情報ｉeは、ｅの型から構築される。
【００９４】
例えば、符号付き５ビット式が与えられ、そして目標マシンの固有ビット幅が１６、３２、４８などであると仮定すると、以下のデータを有する型情報が構築される：
【００９５】
【表３】
0003755733.tif 000004
再度、いくつかの基本データ構造を上記型情報の内部表現のために使用できる。適切なデータ構造は、符号に対してブールフィールド、有効および表現幅に対して２つの整数フィールド、および上位ビット特性に対して２つのブールフィールド（１つはマスク特性のため、他方は符号拡張特性のため）を有する記録構造である。
【００９６】
ステップ３  目標式の内部表現は、再帰的に構築され、そして型情報における適切な上位ビット特性フィールドが設定される。この再帰方法の基本ケースは、ソース式ｅが原子式の場合である；再帰ケースは、ソース式ｅが複合式の場合である。
【００９７】
基本ケース：ｅが原子式ならば、対応の目標原子式が構築される。
【００９８】
１．ｅがソース定数式ｅsならば、目標定数式＜ｉt＞ｅtが構築される。ここで、定数ｅtの値は、その解釈がｅsの解釈と同じとなるようなものであり、型情報ｉtは、ｅtにおける未使用ビットの値にしたがって設定された上位ビット特性を有する型情報ｉe（上記ステップ２で構築された）である。
【００９９】
２．ｅがソース変数式であるならば、目標変数式が構築される。どのソース変数識別子に対しても、一意の目標変数識別子が使用される。より形式的には、ソース変数識別子から目標変数識別子へのマッピングは、完全単射である。ステップ２において構築された型情報ｉeの上位ビット特性フィールドは、ステップ１において構築された上位ビット特性マッピングにおけるエントリにしたがって設定される。ソース変数に対する上位ビット特性マッピングエントリがマスク特性であるならば、マスクフィールドが設定される。同様に、エントリが符号拡張特性ならば、符号拡張フィールドが設定される。エントリが、ソース変数に上位ビット特性が全く割り当てられないことを示すならば、型情報ｉeの上位ビット特性は全く設定されない。
【０１００】
再帰：図６に示されるようなソース複合式ｏｐ（ｅ1，ｅ2，．．．，ｅn）３１は、以下のように目標式に変換される：
１．ソースのオペランドｅ1，ｅ2，．．．，ｅnは、再帰的にこの方法を使用して、まず目標式ｔ1，ｔ2，．．．，ｔnに翻訳される３２。
【０１０１】
２．次に目標式２４は、以下のような目標マシンの演算３３を使用して構築される：
・算術演算において使用される目標サブ式は、オペランドの未使用ビットにおける値がその演算の結果の有効ビットの値に影響し得る場合に、マスキング演算または符号拡張演算に適用される。
【０１０２】
・単に２つ以上の式（＜など）の値を比較する関係演算の場合、有効ビット列の値のみを使用し、目標整数値におけるすべてのビットを使用する値を返す単調演算を適用することで通常十分である。これの効率的な例は、式ｅが与えられたときにｅ＜＜（ｒ−ｗ）を返す演算である。ここで＜＜は、左シフト演算子であり、ｒおよびｗは、ｅの表現および有効幅である。
【０１０３】
・異なる演算（マスキング、符号拡張、単調演算）をターゲットのオペランドの内部表現について使用できる場合、最も安価な目標式を生じる演算が選択される。
【０１０４】
・目標式の型情報ｉtは、演算の値が常にマスクされることが保証され得る場合にマスク上位ビット特性を設定することによって型情報ｉe（上記ステップ２）から構築される；そして同様に、符号拡張上位ビット特性は、演算の値が常に符号拡張されることが保証され得る場合に設定される。このステップは、上記のように注目の算術演算子の第２の特性に依存する。
【０１０５】
再度、内部的に目標式を表すために使用され得るいくつかのデータ構造がある。適切な１つは、リーフノードが原子式を表し、非リーフノードが演算子を表すツリー構造である。
【０１０６】
最後に、図３および５に示されるように、型情報を表すデータは、目標式の最終内部表現から取り出される。
【０１０７】
以下の例において、ソースおよび目標言語が定数、変数、および以下の演算子を伴う複合式を含むと仮定する：
・単項演算子：！、〜、および−。これらの意味は、それぞれＣ言語の単項演算子と同じである。なお、これらの演算子のオペランドの型は、演算の値の型と同じであるという型規則を伴う。
【０１０８】
・２項インフィックス演算子：＋、−、＊、／、％、＆、｜、∧、＆＆、｜｜、＝＝、！＝、＜＝、＞＝、＜、＞、＜＜、＞＞、＞＞、，および＝，これらのセマンティックスは、簡単のためにシフト（＜＜および＞＞）がそれらの第１オペランドのビット幅より大きい値によって定義されない点を除いてそれぞれのＣ言語の２項演算子と同じである。また、以下の型ルールを仮定する。
【０１０９】
１．＝＝、！＝、＜＝、＞＝、＜、＞、＜＜、＞＞および，を除くすべての演算子のオペランドは、それらが返す値と同じ型を有する；
２．関係演算子＝＝、！＝、＜＝、＞＝、＜、および＞のオペランドは、同じタイプを有する；
３．＜＜および＞＞の第１オペランドは、それらが返す値と同じ型を有する；
＜＜および＞＞の第２オペランドは、符号なしである；
４．第２オペランドは、それが返す値と同じ型を有する。
【０１１０】
・以下のフォームの条件文：
ｅ1？ｅ2：ｅ3
このセマンティックスは、Ｃ言語の条件式と同じである。オペランドｅ2およびｅ3は、条件式によって返される値と同じ型を有する。
【０１１１】
・以下のフォームの型キャスト：
（ｔｙｐｅ）ｅ1
ここでｔｙｐｅは、新しい符号（ｓｉｇｎまたはｕｎｓｉｇｎｅｄ）および幅（ｗ）をオペランドｅ1に与えるｓｉｇｎｅｄ  ｗまたはｕｎｓｉｇｎｅｄ  ｗのフォームを有する。この演算の値は、オペランドｅ1が符号付きかつｗより幅が狭い場合、自動的に符号拡張される。
【０１１２】
上記の演算子が与えられると、以下のように簡単なマスキングおよび符号拡張演算が実施され得る：
マスキング  式＜ｉt＞ｔが与えられる場合、型情報ｉtがマスク特性を有するならば、この演算は、単に＜ｉt＞ｔを返す。そうでない場合、式の有効幅がｗであり、かつその表現幅がｒならば、最下位ｗビットが１であり、かつ最上位ｒ−ｗビットが０であるｒビット整数を用いて式の値をマスクする必要がある。この整数をｍと呼ぶ。ｍに関連する型情報ｉmは、ｉt、有効幅ｒおよび表現幅ｒと同じ符号を有する。したがって、必要な式は：
＜ｉ’t＞（＜ｉt＞ｔ＆＜ｉm＞ｍ）
ここでｉ’tは、マスク特性をｉtに設定し、その符号拡張特性を非設定にして得られた型情報である。式ｅが与えられる場合、マスキング演算の適用をｍ（ｅ）によって示す。
【０１１３】
符号拡張  式＜ｉt＞ｔが与えられる場合、型情報ｉtが符号拡張特性を有するならば、この演算は、単に＜ｉt＞ｔを返す。そうでない場合、式の有効幅がｗであり、かつその表現幅がｒならば、ｔの値をｒ−ｗ位置だけ左シフトし、次にｒ−ｗ位置だけ算術演算右シフトするによって符号拡張できる（なお、算術右シフトは、そのオペランドの最上位ビットを保存する）。定数ｒ−ｗをｕで示す。ｕに関連した型情報ｉuは、符号なしであり、有効幅ｒおよび表現幅ｒを有する。ｉtが符号付きならば、必要な式は：
＜ｉ’’t＞（（＜ｉ’t＞（＜ｉt＞ｔ＜＜  ＜ｉu＞ｕ））＞＞  ＜ｉu＞ｕ）
ここでｉ’tは、有効フィールドをｒに設定して正確にされた型情報ｉtである。ｉ’’tは、符号拡張上位ビット特性を設定し、マスク特性を非設定にすることによってｉtから構築された型情報である。
【０１１４】
ｉtが符号なしならば、サブ式：
（＜ｉ’t＞（＜ｉt＞ｔ＜＜  ＜ｉu＞ｕ））
は、右シフトされる前に符号付きｒによって（論理シフトではなく、算術演算右シフトを達成するために）型キャストされる。最後の式は、その符号を維持するために符号なしｒによって型キャストされる。
【０１１５】
式ｅが与えられた場合、符号拡張演算の適用をｍ（ｅ）で表す。
【０１１６】
式ｅが符号なしの場合、ｍ（ｅ）としてｆ（ｅ）を定義し、他方ｅが符号付きの場合、ｓ（ｅ）と定義する。また、＝＝、！＝、＜、＜＝、＞および＞＝を伴う関係演算の翻訳の間に必要な以下の単調演算を定義する。
【０１１７】
単調演算  有効幅ｗおよび表現幅ｒを有する式＜ｉt＞ｔが与えられた場合、この演算は、以下を返す：
＜ｉ’t＞（＜ｉt＞ｔ＜＜  ＜ｉu＞ｕ）
ここで、ｕはｒ−ｗ、型情報ｉ’tはｉt、有効幅ｒ、および表現幅ｒと同じ符号を有する。型情報ｉuは、符号なしであり、有効幅ｒおよび表現幅ｒを有する。式ｅが与えられた場合、この単調演算の適用をｍｎ（ｅ）で表す。
【０１１８】
マスキング、符号拡張、および上記単調演算のより効率的な実施が可能であるが、上記の実施でも本発明明細書中に記載される翻訳機構の正確さに対しては十分である。
【０１１９】
より効率的な実施には、式の効率を向上するために最適化変換を応用した技術を使用する。以下は、演算に応用することのできる変換である：
フォームｔおよびｍのマスク演算ｅは、以下のように最適化され得る：
・ｔが定数ｋならば、ｅの値は、例えばｌに計算され、そしてｅはｌによって置換される。
【０１２０】
・ｔがフォームｘ＆ｋまたはｋ＆ｘ（ここでｋは定数）ならば、ｋおよびｍの値は、例えばｌに計算され、そしてｅはｔ＆ｌによって置換される。
【０１２１】
・ｔがｘ＆ｙ（ここでｘ＆ｍまたはｙ＆ｍのいずれか（または両方）が、例えばｘ’およびｙ’に最適化され得る）ならば、ｅはｘ’＆ｙ’によって置換される。同様の規則がフォームｘ｜ｙ、ｘ∧ｙ、ｚ？ｘ：ｙの演算に対して適用される。
【０１２２】
フォーム（ｔ＜＜ｕ）＞＞ｕの符号拡張演算ｅは、以下のように最適化され得る：
・ｔが定数ｋならば、ｅの値は、例えばｌに計算され、そしてｅはｌによって置換される。
【０１２３】
・ｔがフォームｘ＜＜ｋ（ここでｋは定数）ならば、ｋ＋ｕの値は、例えばｌに計算され、そしてｅは（ｔ＜＜ｌ）＞＞ｕによって置換される。
【０１２４】
・ｔがｘ＆ｙ（ここで（ｘ＜＜ｕ）＞＞ｕまたは（ｙ＜＜ｕ）＞＞ｕのいずれか（または両方）が、例えばｘ’およびｙ’に最適化され得る）ならば、ｅはｘ’＆ｙ’によって置換される。同様の規則がフォームｘ｜ｙ、ｘ∧ｙ、ｚ？ｘ：ｙの演算に対して適用される。
【０１２５】
フォームｔ＜＜ｕの単調演算ｅは、以下のように最適化され得る：
・ｔが定数ｋならば、ｅの値は、例えばｌに計算され、そしてｅはｌによって置換される。
【０１２６】
・ｔがフォームｘ＜＜ｋ（ここでｋは定数）ならば、ｋ＋ｕの値は、例えばｌに計算され、そしてｅはｔ＜＜ｌによって置換される。
【０１２７】
・ｔがｘ＆ｙ（ここでｘ＜＜ｕまたはｙ＜＜ｕにいずれか（または両方）が、例えばｘ’およびｙ’に最適化され得る）ならば、ｅはｘ’＆ｙ’によって置換される。同様の規則がフォームｘ｜ｙ、ｘ∧ｙ、ｚ？ｘ：ｙの演算に対して適用される。
【０１２８】
多くの式から最も効率的な式を選択することが必要となることがあり得る。多くの式ｅ1，．．．，ｅnが与えら得れた場合、ｅ1，．．．，ｅnのうちで最も効率的に計算される可能性のある式を表すために用語「ｅ1，．．．，ｅnのうちの最も安価なもの」を使用する。また、ｅの計算およびそれに続くｅ’の計算が最も効率的である可能性があるように式のペアについての用語：「（ｅ1，ｅ’1），．．．，（ｅn，ｅ’n）のうちの最も安価なものが（ｅ1，ｅ’1），．．．，（ｅn，ｅ’n）における（ｅ，ｅ’）の式のペアである」を定義する。目標式の効率の良好な尺度は、その内部表現における演算子の数である：
最も安価な式は、演算子の数が最も少ない式である。
【０１２９】
ある型情報ｉ1が忠実にされた型情報ｉ2であるのは、ｉ2が符号なしの場合にマスク上位ビット特性を設定することによって、およびｉ2が符号付きの場合に符号拡張上位ビット特性を設定することによって、ｉ1をｉ2から構成する場合であるとする。
【０１３０】
ここでソース式を目標式に翻訳するための方法を説明する：
・上記のようにソース言語における定数および変数が目標定数および変数に変換される。
【０１３１】
・以下のフォームの単項演算子ｅが与えられる：
ｏｐ（ｅ1）
まず、ｅの型から型情報ｉtを構築し（ｉtは上位ビット特性を全く有さない）、次にオペランドｅ1を再帰的にｔ1に変換する。式ｔ1は、上記の内部表現によって表されるので、その型化情報を用いて注釈をつけられる。必要な目標式：
＜ｉ’t＞ｏｐ（ｔ’1）
が次に構築される。ここで、演算子ｏｐが：
！：式ｔ’1は、ｔ1の未使用ビットの値が！演算の結果における有効ビット列に影響を与え得るので、マスクまたは符号拡張される必要がある。したがって、式ｍ（ｔ1）およびｓ（ｔ1）が構築され、そしてｔ’1がその２つのうちの安価な方となるよう選択される。型情報ｉ’tは、忠実にされた型情報ｉtである。
【０１３２】
〜：必要なオペランドｔ’1は、ｔ1における未使用ビットが〜演算の結果における有効ビット列に影響を与えないので、単にｔlである。型情報ｉ’tは、ｔ1が符号拡張される場合かつその場合に限り符号拡張特性を設定することによって、ｉtから構築される。
【０１３３】
−：必要なオペランドｔ’1はｔ1であり、かつ型情報ｉ’tはｉtである。なぜなら、算術否定演算−の値は、常にマスクおよび／または符号拡張されることが保証されないからである。
【０１３４】
・以下のフォームの２進演算ｅが与えられる場合：
ｅ1  ｏｐ  ｅ2
まず、ｅの型から型情報ｉtを構築し、オペランドｅ1およびｅ2をそれぞれｔ1およびｔ2に変換する。必要な目標式は：
＜ｉ’t＞（ｔ’1  ｏｐ  ｔ’2）
ここで、演算子ｏｐが：
＋、−、＊：オペランドｔ’1およびｔ’2は、それぞれｔ1およびｔ2である。型情報ｉ’tは、ｉtである。
【０１３５】
／、％：オペランドｔ’1およびｔ’2は、それぞれｆ（ｔ1）およびｆ（ｔ2）である。型情報ｉ’tは、忠実にされたｉtである。
【０１３６】
＆＆、｜｜：オペランドｔ’1は、ｍ（ｔ1）およびｓ（ｔ2）のうちのより安価な方である。オペランドｔ’2は、ｍ（ｔ2）およびｓ（ｔ2）のうちのより安価な方である。型情報ｉ’tは、忠実にされたｉtである。
【０１３７】
＆：オペランドｔ’1およびｔ’2は、それぞれｔ1およびｔ2である。型情報ｉ’tは、ｔlまたはｔ2のいずれかがマスクされた場合にマスク特性を設定し、次にｔlおよびｔ2の両方が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
【０１３８】
｜、∧：オペランドｔ’1およびｔ’2は、それぞれｔ1およびｔ2である。型情報ｉ’tは、ｔlおよびｔ2の両方がマスクされた場合にマスク特性を設定し、次にｔlおよびｔ2の両方が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
【０１３９】
＝＝、！＝：オペランド（ｔ’1，ｔ’2）のペアは、（ｍ（ｔ1），ｍ（ｔ2））、（ｓ（ｔ1），ｓ（ｔ2））、および（ｍｎ（ｔ1），ｍｎ（ｔ2））のうちの最も安価なものである。型情報ｉ’ｔは、忠実にされたｉtである。
【０１４０】
＜＝、＞＝、＜、＞：オペランド（ｔ’1，ｔ’2）のペアは、（ｆ（ｔ1），ｆ（ｔ2））、および（ｍｎ（ｔ1），ｍｎ（ｔ2））のうちの安価な方である。型情報ｉtは、忠実にされたｉtである。
＜＜：第１オペランドｔ’1は、式ｔ1であり、第２オペランドｔ’2は、ｆ（ｔ2）である。型情報ｉ’tは、ｉtである。
【０１４１】
＞＞：オペランドｔ’1およびｔ’2は、それぞれｆ（ｔ1）およびｆ（ｔ2）である。型情報ｉ’tは、忠実にされたｉtである。
＝：第１オペランドｔ’1は、単に式ｔ1である。第２オペランドｔ’2は、ｔ’1がマスクされた場合にｍ（ｔ2）となり、ｔ’1が符号拡張された場合にｓ（ｔ2）となり、その他の場合はｔ2となる。型情報ｉ’tは、ｔ’2がマスクされた場合にマスク特性を設定し、次にｔ’2が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
，：オペランドｔ’1およびｔ’2は、ｔ1およびｔ2である。型情報ｉ’tは、ｔ2がマスクされた場合にマスク特性を設定し、次にｔ2が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
【０１４２】
・以下のフォームの条件付き式ｅが与えられた場合：
ｅ1？ｅ2：ｅ3
まず、型情報ｉtをｅの型から構築し、次にオペランドｅ1、ｅ2、およびｅ3をそれぞれｔ1、ｔ2，およびｔ3に変換する。必要な目標式は：
＜ｉ’t＞（ｔ’1？ｔ2：ｔ3）
ここで、ｔ’1は、ｍ（ｔ1）およびｓ（ｔ1）の安価な方である。型情報ｉ’tは、ｔ2およびｔ3の両方がマスクされた場合にマスク特性を設定し、次にｔ2およびｔ3の両方が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
【０１４３】
・以下のフォームの型キャスト式ｅ：
（ｔｙｐｅs）ｅ1
は、以下に示すように必要な目標式に変換される。
【０１４４】
１．型情報ｉtは、型ｔｙｐｅsから構築される。ｓtおよびｒtをそれぞれＩtの有効幅および表現幅として定義する。ｔｙｐｅsを必要な目標式の型として定義する；すなわち、ｔｙｐｅtは、幅ｒtおよびｔｙｐｅsの符号を有する。
【０１４５】
２．オペランドｅ1は、式ｔ1に変換される。ｓ1およびｒ1をそれぞれｔ1の有効幅および表現幅として定義する。
【０１４６】
３．ｓtがｓ1と同じならば、目標式は：
＜ｉt(t1)＞（ｔｙｐｅt）ｔ1
であり、ここでｉt(t1)は、ｔiがマスクされた場合にマスク特性を設定し、次にｔ1が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。
【０１４７】
４．ｓtがｓlより小さいならば、目標式は：
＜ｉt＞（ｔｙｐｅt）ｔ1
である。
【０１４８】
５．ｓtがｓ1より大きいならば、目標式は：
（ａ）ｒtがｒlと同じならば、目標式は：
＜ｉt(f(t1))＞（ｔｙｐｅt）ｆ（ｔ1）
であり、型情報ｉt(f(t1))は、ｆ（ｔ1）がマスクされた場合にマスク特性を設定し、次にｆ（ｔ1）が符号拡張された場合に符号拡張特性を設定することによって、ｉtから構築される。これは、型情報ｉt(f(t1))を忠実にしない。なぜなら、ｆ（ｔ1）の符号は、ｔｙｐｅtにおける符号と異なるからである。
【０１４９】
（ｂ）ｒtがｒlよりも大きいならば、目標式は：
＜ｉ’t＞（ｔｙｐｅt）ｆ（ｔ1）
であり、ここでｉ’tは、忠実にされたｉtである。
【０１５０】
ここで以下のソース式を１６ビットアーキテクチャによってシミュレーションされ得る目標式に翻訳することによりこの方法を例示する：
（（ａ(U5)＋ｂ(U5)）＊ｃ(U5)）／（ｄ(U5)＋ｅ(U5)）。
【０１５１】
所与のソース式は、元から型適正である。
【０１５２】
ステップ１：ソース式におけるいずれの変数も「上位ビット特性なし」エントリと関連づける自明上位ビット特性マッピングを構築する。
【０１５３】
ステップ２：型情報データ構造が構築される。ソース式の型は符号なし５であり、目標アーキテクチャは１６ビットであり、以下の型情報が構築される：
【０１５４】
【表４】
0003755733.tif 000005
所与のソース式におけるすべてのサブ式が同じ型を有するので、上記のデータは、この方法の再帰部分の間に各サブ式に対して構築される。以下のように表記：
＜上位ビット特性＞式
を使用して、いくつかの特定の上位ビット特性を注釈された所与の目標式を表す。
【０１５５】
ステップ３：目標ソース式が以下のように再帰的に構築される：
１．ソース式ｓから：
（（ａ(U5)＋ｂ(U5)）＊ｃ(U5)）／（ｄ(U5)＋ｅ(U5)）
２つのオペランド：
ｓ0＝（（ａ(U5)＋ｂ(U5)）＊ｃ(U5)）
ｓ1＝（ｄ(U5)＋ｅ(U5)）
が、以下のようにｔ0およびｔ1に再帰的に翻訳される：
（ａ）ソース式ｓ0から、２つのオペランド：
ｓ00＝ａ(U5)＋ｂ(U5)
ｓ01＝ｃ(U5)
が、以下のようにｔ00およびｔ01に再帰的に翻訳される：
ｉ．ソース式ｓ00から、２つのオペランド：
ｓ000＝ａ(U5)
ｓ000＝ｂ(U5)
が、単に各ソース変数に対する一意の目標変数を構築し、以下を与えることによってｔ000およびｔ000に再帰的に翻訳される：
ｓ000＝＜ｎｏｎｅ＞ａ(U5)
ｓ000＝＜ｎｏｎｅ＞ｂ(U5)。
【０１５６】
ステップ２において構築された上位ビット特性マッピングは、上記の変数には上位ビット特性を割り当てず、そこでｎｏｎｅを設定する。
【０１５７】
ｉｉ．ｓ00に関する演算子は＋であるので、２つのオペランドｔ000およびｔ001について値補正演算子を適用する必要はない、そこで以下の目標式ｔ00が構築される：
ｔ00＝＜ｎｏｎｅ＞ａ(U16)＋ｂ(U16)
上位ビット特性は保証され得ず、そこでｎｏｎｅを設定する。
【０１５８】
ｉｉｉ．ソース式ｓ01が、ソース変数に対する一意の目標変数を単に構築し、以下を与えることによってｔ01へ再帰的に翻訳される：
ｔ01＝＜ｎｏｎｅ＞ｃ(U16)。
【０１５９】
ステップ２において構築された上位ビット特性マッピングは、上記変数に上位ビット特性を割り当てず、そこでｎｏｎｅを設定する。
【０１６０】
（ｂ）ｓ0に関する演算子は＊であるので、２つのオペランドｔ00およびｔ01について値補正演算子を適用する必要はない。そこで、以下の目標式ｔ0が構築される：
ｔ0＝＜ｎｏｎｅ＞（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）。
【０１６１】
上位ビット特性は保証され得ず、そこでｎｏｎｅがセットされる。
【０１６２】
（ｃ）ソース式ｓ1から、２つのオペランド：
ｓ10＝ｄ(U5)
ｓ11＝ｅ(U5)
は、各ソース変数に対する一意の目標変数を単に構築し、以下を与えることによってｔ10およびｔ11へ再帰的に翻訳される：
ｔ10＝＜ｎｏｎｅ＞ｄ(U16)
ｔ11＝＜ｎｏｎｅ＞ｅ(U16)。
【０１６３】
ステップ２において構築された上位ビット特性マッピングは、上記変数に上位ビット特性を割り当てず、そこでｎｏｎｅを設定する。
【０１６４】
（ｄ）ｓ1に関する演算子は＋であるので、２つのオペランドｔ10およびｔ11について値補正演算子を適用する必要はない。そこで、以下の目標式ｔ1mが構築される：
ｔ1＝＜ｎｏｎｅ＞（ｄ(U5)＋ｃ(U5)）。
【０１６５】
上位ビット特性は保証され得ず、そこでｎｏｎｅを設定する。
【０１６６】
２．ｓに関する演算子は／であるので、目標式ｔ0およびｔ1は、以下を与えるマスキング値補正演算に適用される：
ｔ0’＝＜ｍａｓｋｅｄ＞（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）＆３１(U16)
ｔ1’＝＜ｍａｓｋｅｄ＞（ｄ(U16)＋ｅ(U16)）＆３１(U16)
そして、目標式：
ｔ＝＜ｎｏｎｅ＞
（（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）＆３１(U16)）／
（（ｄ(U16)＋ｅ(U16)）＆３１(U16)）
が構築される。マスク特性は、符号なし演算の結果において保証され得るので、マスク上位ビット特性が設定され、以下の目標式ｔの最終の内部表現を与える：
＜ｍａｓｋｅｄ＞
（（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）＆３１(U16)）／
（（ｄ(U16)＋ｅ(U16)）＆３１(U16)）。
【０１６７】
最後の段階は、上記式から追加型情報を取り出し、以下を与える：
（（（ａ(U16)＋ｂ(U16)）＊ｃ(U16)）＆３１(U16)）／（（ｄ(U16)＋ｅ(U16)）＆３１(U16)）。
【０１６８】
この技術は、特定の目標マシン上の算術演算回路の高級記述の効率的なシミュレーションにおいて使用される。図７は、Ｂａｃｈハードウェア設計フローの例を示す。ここでハードウェアは、Ｂａｃｈ高級言語で記述される。ハードウェア記述は、４０で実施され、Ｂａｃｈソースコードを生成する。ステップ４１は、Ｂａｃｈハードウェア記述をシミュレーションし、上記の方法を使用して、目標マシンの算術演算および／または論理回路において実施される演算処理または式の翻訳を提供する。シミュレーションの結果は、４２で正確さについて検査される。不正確であれば、新しいインプリメンターションがステップ４０において実行される。シミュレーション結果が正確であるならば、ステップ４３が低級ハードウェア記述を生成し、次にその低級ハードウェア記述は、公知または適切な技術を使用してシリコンチップ４４に変換される。
【０１６９】
【発明の効果】
所定のビット幅の整数算術演算式を計算する能力があるだけの所定のデバイスを使用して、算術演算および任意のビット幅の整数を伴う関係式の効率的な計算を行う方法を提供することができる。
【０１７０】
いくつかの特定の幅（例えば、ｗ1、ｗ2など）の整数算術演算を計算することのできる、目標マシンと呼ばれる所定のデバイスまたは機構に対して、上記の方法は、任意の幅の整数を伴う算術演算式を特定の幅の整数を伴う効率的な算術演算に翻訳する。
【図面の簡単な説明】
【図１】図１は、本発明の実施態様の翻訳方法を例示するフロー図である。
【図２】図２は、図１に例示される方法を実行するためのコンピュータのブロック模式図である。
【図３】図３は、本発明の別の実施態様の翻訳方法を例示する模式フロー図である。
【図４】図４は、ソース整数およびそれが翻訳された目標整数のビット構造を例示する図である。
【図５】図５は、図３に示される方法において使用される目標マシン式を表すための内部データ構造を例示する図である。
【図６】図６は、複合ソース式の目標式への翻訳を例示する高級フロー図である。
【図７】図７は、集積回路の形態のハードウェアの設計および実施において図３の方法を使用する例を示す模式フロー図である。
【図１】
0003755733.tif 000006
【図２】
0003755733.tif 000007
【図３】
0003755733.tif 000008
【図４】
0003755733.tif 000009
【図５】
0003755733.tif 000010
【図６】
0003755733.tif 000011
【図７】
0003755733.tif 000012