JPS5854449A - 分岐命令短縮化処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は、命令カウンタ相対の分岐命令にシ冒−トタイ
プの分岐命令が含まれる計算機システムにおいて、プロ
ゲラにング言語の！＆埋プｐセッサにおけるオブジェク
ト・プログラム中の分岐命令を鋏シ嘗−トタイプの分岐
命令で置換し、命令サイズの短縮化を図るための処理方
式に関する。

分岐命令には、現アドレスから分岐先アドレスまでの距
離が比較的短い一定値ＩＣ１１１ｉｌされているシＷ−
Ｆタイプのものと、その制限のないロングタイプのもの
とがある。通常、コンパイル４６１１時のオブジェクＦ
・プログラム中の分岐命令としては、第一次的にはすべ
てロングタイプの分岐命令が使用される。しかし１分岐
命令がプログラム中に現われる頻度は比較的高いために
、可能な限り命令サイズが小さく奥行時間が速いシ璽−
トタイプ分岐命令を使用することが、メ％９容量の節約
とオブジェクドブ冒グラムの高速化のために望まれる。

このため、従来から窒ングタイプの分岐命令なシ欝−ト
タイプの分岐命令に置換するＪ６１１カ行なわれていた
。

従来性われていた分岐命令のシ冒−トタイプ化技法には
いくつかの方法が知られているが、どの方法をとっても
分岐先のアドレスを格納しておくために大きなテーブル
が必要であり、短縮化を実現するためには十分なメモリ
サイズがなければならないという欠点があうた。

本発−の目的は、オブジェクト・プログラム中に含まれ
る分岐命令をシ１−トタイプの命令に変換する処理に使
用されるテーブルのサイズを必要最小限ですむよ５に制
限するテーブル制御方式を提供するととｋある。

そのため９本発明は、シ璽−トタイプの分岐命令を有す
る計算機システムにおいて、アドレス・カウンタの指示
にしたがいオブジェクト・プログラムを順次読取り、ラ
ベルの定義および分岐命令を検出する手段と、各エント
リが、ラベル、＃ラベルの定義位置のアドレス、該ラベ
ルを参照している分岐命令位置のアドレス、および短縮
化処理の済・未ｖ！によりエントリの無効・有効を表示
するフラグからなるとともに前記検出手段の出力データ
が登録される複数のエントリで構成されているツペルー
テーブル手段と、該２ベル・テーブルの探索および更新
を行なうテーブル管理手段と。

ツヘル拳テーブル中に登録されているアドレスとアト１
゛レス・カウンタの現在値との差を計算し、その差がシ
曽−トタイプ分岐命令の許容最大飛び欠相対アドレス範
囲内にあるか否かを判定する判定手段と、諌判定結果に
基づいてシ曹−トタイプ分岐命令の置換部層を行なう置
換手段とをそなえ。

前記ラベル・テーブルのエントリ数は、シ璽−トタイプ
分岐命令の許容最大飛び欠相対アドレス値を最小命令サ
イズで除した値Ｋｆｉば等しく定め。

更に前記テーブル管理手段は、新エントリが前記フラグ
が無効表示となうているエントリ、あるいはすでにアド
レス距離が許容範囲外となっているエントリの位置に設
定されるよう連続的にテーブル制御を行なうことを特徴
とするものである。

次に２本発明を痰論例にしたがって詳述する。

以下は２本発明を；ンパイツのオブジェクト−プログツ
五最適化の一部として実施した場合についてのものであ
る。

ここで用いられるシ璽−トタイプの分岐命令の相対アド
レス範囲は−１２８〜＋１２７（バイトアドレス）であ
るものとする。

ＪＩＩＩＩＩＸ、ψ）、−）は２本発明の１実施例の説
明図である。

第１図（Φにおいて、ｌはオブジェクト・プログラム、
２はアドレス・カウンタ、３はラベル・テーブル、４は
空きエントリ・ポインタを示す。アドレス・カウンタ２
はオブジェクト・プログラム１の処理をどこまで行なっ
たかを示すポインタであり、また空きエントリ・ポイン
タ４はラベル自テーブル３の空きエントリを示すポイン
タである。

テーブル３へのアドレス登録は、空きエントリ・ポイン
タ４の指すエントリに行なわれる。２ベル・テーブル３
の各エントリは、オブジェクト−プログラム１中ｋｐｍ
われるラベルと、−）ベルが定義されている位置のアド
レスと、該ラベルを参照している分岐命令の位置のアド
レスと、アドレスを格納する項目が空ぎエントリか否か
を示すフラグビットとｋよって構成されている。フラグ
ビットは、＠０１のとき９鎗エントリを、°１”のとき
有効エントリを示す。

＄１１１１１１）は、動作の初期設定状態を示し、アド
レス・カウンタ２はオブジェクト・プログラム１の先願
位置を指し、空きエントリポインタ４もうベル・テーブ
ル３の先頭位置を指している。第１図向は、ブーグラム
１のアドレスａで２ペルＬ１への分岐命令を検出し、ア
ドレスｂでラベル３の定義を検出して、各各のデータを
ラベル・テーブル３に登録した状態を示す。

この場合のように１分岐命令の飛び先ラベルＬ１かいま
だラベル・テーブル中に登録されていないときＫは、ラ
ベルＬ１のアドレスが不明なので。

飛び先アドレスまでの距離が算出できず、この分岐命令
をシ冒−トタイプ化できるかどうかはまだわからない状
態にある。したがって、この分岐命令のアドレスａは、
ラベルテーブル中に登録して残しておかれる。

第１１１（Ｃ）は、アドレスｄまで躯埋が進んだ状態を
示す、このとき、アドレスＣでラベルＬ１の定義を見出
しており、第１ｍ（６）で登録されていたＬｌへの分岐
命令に対してそのアト−レスａとの差Ｃ−ａ≦１２７が
成り立つか否かを判定する。これが成す立ツ場合には、
シ璽−トタイプの分岐命令に変換する操作を行なうとと
もに、この分岐命令のアドレスが登録されていたエント
リのフラグビットを無効表示にして、以降の処理のため
に使用可能な空きエントリとする。

次に、アドレスｄＫある分岐命令に対しては。

その参照ラベルＬ２がアドレスｂですでにテーブルに登
録されているので、そのアドレスｂとアドレス・カウン
タの値ｄとの差ｄ−ｂ≦１２８を判定し、これが成り立
てば１分岐命令のシ謬−トタイプ化を行なう。そしてこ
の場合にはアドレスｄの登録は行なわれない。

上記のような地理を続けて行く途中で空きエントリ・ポ
インタがラベル・テーブルの終りまでくれば１次に再び
ラベル・テーブルの先１ｊｋ戻るよ５に制御される。空
きエントリの探索は、９鯉エントリを示すフラグビット
＠Ｏ”をもつものと。

フラグビットが＠ｌ”であうても定義アドレスあるいは
参照アドレスと現在のアドレスカウンタの値との差が１
２８を越えているものとを調べればよい、何故ならば、
フラグビットが＠Ｏ”であるということは、初期設定の
未使用状態あるいはシ冒−トタイプ化処理済のエントリ
であることを示し。

また現在のアドレス・カクンタ値との差が１２８以上離
れたアドレスにあるラベルの定義あるいは分岐命令は、
シ冒−トタイプ分岐命令の条件からすでに外れるからで
ある。

したが、て、ラベルチーペル３の中には、アドレスカウ
ンタの値との差が１２８を越えないアドレスをもつ分岐
命令またはラベルの定義のエントリだけを保持すればよ
いととになる。対象となる計算機における最小サイズの
命令のバイトをｍ、また最小サイズの分岐命令のバイト
数を露とすれば。

テーブルのエントリ数の上限は次式で与えられる。

１２＄　＋１２７ ｔｎ　　　　　　　　ｎ これは、もっとも多くのエントリ数を必要とする場合は
−１２８〜＋１２７の範囲にラベル定義と分岐命令とが
半々に存在し、しかもそれらの関に結合が起きていない
とぎであり、またシ冒−トタイプ分岐命令の制限された
一定のバイトアドレス領域内にもっとも多くの命令が詰
め込まれるのは最小サイズの命令が連続している場合で
あることによっている。

本実施例では、ｍｘｌｌ＝３（バイト）なので１２７エ
ントリあれば十分である。

第２図は、上述した実施例方式の概略的機能関連図であ
る。

図において、アドレスカウンタ２の指示にしたがって、
オブジェクト・プログ２ム読敞り・検出部５でオブジェ
クト・プμグラムの読堆りが行なわれ、定義ラベルと１
分岐命令およびその参照ラベルとが続出される。読み出
されたラベルについて、ラベル・テーブル探索部６でラ
ベル・テーブルの探索が行なわれる。同一ラベルが見出
された場合には、アドレス距離計算・判定部７で現在の
アドレス値との距離を計算され、それがシ諺−トタイプ
分岐命令に許容される所定の範囲内にあれば、シ謬−ト
タイプ分岐命令置換処理部８で対象となっているｐング
タイプ分岐命令をシ冒−トタイプ分岐命令に置換する。

他方、６のラベル・テーブル探索において同一ラベルを
見出せなかった場合には、ラベル・テープル登録部９で
ラベル・テーブルへの登録処理が行なわれる。

との登録処理は、該ラベルが分岐命令に先行する定義ラ
ベルである場合に、第１図（φに示すラベル・テーブル
３のラベルおよび定義アドレス欄にラベルとアドレスと
を記入して、後に出現するであろう分岐命令のために＃
ラベルが待機状１１にあることを表示し、また酸ラベル
が定義ラベルに先行する分岐命令の参照ラベルである場
合＃Ｉｃは、腋ラベルとアドレスとをラベル・テーブル
３のラベルおよび参照アドレス欄に記入し、骸分岐命令
が後に出現するであろう定義ラベルのために待機状態に
あることを表示するものである。登鎌Ｊ６１１と同時に
そのエントリのフラグ・ビットを１１＠にセットし、誼
エントリのデータは有効であって破壊し【はならないこ
とを表示する。

更に、１のアドレス距離計算によってシ、−トタイプ分
岐命令の使用可能条件の範囲外であることがわかった場
合には、ラベル・テーブルエントリ無効化ｗａｓｔｏで
誼ラベルに関連する二ンＦすのフラグを空き（無効）表
示“０”にリセットする。フラグ＠０”をもつエントリ
は、空きエントリ拳ポインタ４によってポインタ指示さ
れかつデータ記入要求が生じたとき、に、空きエントリ
として新らしいデータのために使用される。

ｇａａ！ｉｌは、ラベル−テーブル３の空きエントリ位
置を指示するためのポインタ制御機構の実施例を示す。

図においＣ，空きエントリ・ポインタ４は、その内容を
＋１回路１１によって１ずつ歩道されるととｋよってラ
ベル−テーブルを順次的にスキャンし、空きエントリが
検出されたとき＋１回路の機能を停止させるものである
。＋１回路１１が動作を停止される場合は、ラベル・テ
ーブル３中のエントリのアドレス欄１２または１３の値
が、アドレス・カウンタ２の現在値に対して１機能ブロ
ック１５または１６に示す条件を満たさないとき。

あるいはフラグ１４が空き（無効）エントリ表示＠Ｏ”
を示しているときであり、これらの場合に不動作となる
よ５０Ｒ回路１７を介して制御される。この空ぎエント
リ・ポインタ動作は、ラベル・テーブルに新エントリの
設定が必要と４なるととに起動される。

このよ５に、ラベル・テーブルは新スペースが必要とな
る都度不要になりたデータを次々と追い出すととによっ
て必要最小限の大きさで十分機能を果すことができる。

第４１１は、上述した実施例のための最適化プログラム
で用いるラベル・テーブルの管理モジ＾−ルのフ■−図
である。このモジ暴−ルは、ラベル・テーブルの初期設
定と、ラベル定義アドレスの登鎌と、ラベルを飛び先と
して参照している分岐命令のアドレス、登録との各ルー
チンで構成され。

オブジェクト・プログラム中９ラベル定義および分岐命
令を検出してそれらのアドレスをテーブルに登鎌する躯
瑠と分岐命令のシ璽−トタイグ化とを行なう。

以上１本発＠について説明したよ５に、本発明によれば
６分岐命令のシ曹−トタイプ化処１１に便用するテーブ
ルのエントリ数を必要最小限にすることができるので、
メモリサイズを小さく設計することが可能となる。

【図面の簡単な説明】

第１図（φ乃至＜Ｃ）は本発明の詳細な説明図、第２図
は本実施例の機態関連図、第３図は本実施例における空
きエントリポインタ制御部の構成図、第４図は本実施例
のための処理ルーチンのフロー図である。 図中、１はオブジェクト・プログラム、２はアドレス−
カウンタ、３はラベル・テーブル、４は空きエントリ・
ポインタを示す。 特許出願人　富士通株式会社 代理人弁理士　森　１）　　　寛 （ａ） （ｂ） 才　３　目 ［

Claims (1)

【特許請求の範囲】
1. シ１−トタイプの分岐命令を有する計算機システムにお
   いて、アドレス・カウンタの指示にしたがいオブジェク
   ト・プ３グッムを順次読取り、ラベルの定義および分岐
   命令を検出する手段と、各エントリが、ラベル、皺ツペ
   ルの定義位置のアドレス、鋏ツベルを参照している分岐
   命令位置のアドレス、および短縮化ＩＩ＆唾の済・未済
   によりエントリの無効・有効を表示するフラグからなる
   とともに前記検出手段の出力データが登録される複数の
   エントリで構成されているラベル・テーブル手段と、該
   ラベル・テーブルの探索および更新を行なうテーブル管
   理手段と、Ｉ）ベル・テーブル中に登録されているアド
   レスとアドレス・カウンタの現在値との差を計算し、そ
   の差がシ冒−トタイプ分岐命令の許容最大飛び欠相対ア
   ドレス範囲内にあるか否かを判定する判定手段と、該判
   定結果に基づいてシ曹−トタイプ分岐命令の置換Ｊ６種
   を行なう置換手段とをそなえ、前記ラベル・テーブルの
   エントリ数は、シ謬−トメイプ分岐命令の許容最大飛び
   欠相対アドレス値を最小命令サイズで除した値Ｋｆｉぼ
   等しく定め、更に前記テーブル管理手段は、新エン）９
   が前記フラグが無効表示となっているエントリ、あるい
   はすでにアドレス距離が許容範囲外となっているエント
   リの位置に設定されるよう連続的にテーブル制御を行な
   うことを特徴とする分岐命令短縮化ＩＩ＆垣方式。