JPH0776927B2 - コンパイル方法 - Google Patents

コンパイル方法

Info

Publication number
JPH0776927B2
JPH0776927B2 JP61266812A JP26681286A JPH0776927B2 JP H0776927 B2 JPH0776927 B2 JP H0776927B2 JP 61266812 A JP61266812 A JP 61266812A JP 26681286 A JP26681286 A JP 26681286A JP H0776927 B2 JPH0776927 B2 JP H0776927B2
Authority
JP
Japan
Prior art keywords
registers
graph
node
register
allocation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP61266812A
Other languages
English (en)
Other versions
JPS62144247A (ja
Inventor
アシユフアク・アブダルレマン・ミユンシ
カール・マツクス・シンプフ
Original Assignee
インタ−ナショナル ビジネス マシ−ンズ コ−ポレ−ション
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by インタ−ナショナル ビジネス マシ−ンズ コ−ポレ−ション filed Critical インタ−ナショナル ビジネス マシ−ンズ コ−ポレ−ション
Publication of JPS62144247A publication Critical patent/JPS62144247A/ja
Publication of JPH0776927B2 publication Critical patent/JPH0776927B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/441—Register allocation; Assignment of physical memory space to logical memory space

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Complex Calculations (AREA)

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明はスカラプロセツサ又はベクトルプロセツサのい
ずれかで、原始コードをマシの実行可能なコードにコン
パイルする際に、レジスタの割当ての最適化を行うコン
パイラに関する。
B.従来技術及びその問題点 コンパイラ構成に関する標準的な著作の中で、Aho等に
よる“Principles of Compiler Design"、Addision−We
sley Publishing Co.,1977、及びWaite等による“Compi
ler Construction"、Springer−Verlag,1984は、PASCAL
やFORTRAN等のコンピユータの原始言語を、目的計算機
によつて実行可能なコードに変換する場合、一連の変換
によつて行なわれることを指摘している。まず、原始記
号例は字句解析されて、翻訳のためのアトミツク単位す
なわちワードが確定され、次に構文解析されて、ワード
間の文関係を確定する。この出力は、「解析木」の形で
表現される。この解析木は、原始コードの中間言語表現
に変換される。大抵のコンパイラは、解析木を明示的に
生成しないが、構文解析が生じるように中間コードを形
成する。次に、最適化が中間コードに適用され、その
後、目的計算機の実行可能コード、すなわち目的コード
が生成される。
コンパイラが実行しなければならないタスクの中には、
原始コード命令のストリームによつて指定される計算が
効率よく完了されることができるように、計算資源が割
り付け及び割り当てられる使用可能な「資源」の中に
は、ALUのような計算機構、入出力、レジスタを含むメ
モリ、及び、オペレーティングシステム要素等が含まれ
る。コンパイラの最適化部の目的は、（ａ）コードサイ
ズを縮小する（ｂ）可能な場合、実行速度を増大する
（ｃ）資源割り付けにより、コストを最小限にすること
にある。資源使用又は消費パターンのスケジユールは、
コンパイルされるコードに埋め込まれる。
命令ストリームはグラフ構成に写像されることができ、
グラフ理論の特性を利用することができることは周知で
ある。コード列は、局所最適化に対して基本ブロツクの
グラフ特性により、そして大域最適化に対して基本ブロ
ツクのフローグラフにより解析される。
基本ブロツクとは、連続した文の列からなる。この列は
開始においてのみ入力され、入力されると、この文は停
止又は分岐の可能性もなく（ただし、列の終わりは除
く）順次実行される。
フローグラフは、基本ブロツク間の制御フローを記述す
る。フローグラフは、例えば、反復計算又は再帰計算に
必要な基本ブロツク間のループ、分岐及びネステイング
動作を示す。
データ依存の閉路のない有向グラフ（DAG）は、基本ブ
ロツクを解析するためのデータ構造である。例えば、ａ
＝ｓ＋ｃは、ｂ＋ｃにより、それぞれの辺を通して各々
が共通節点Ｃに接続される開始節として表現される。フ
ローグラフの各節点又は（基本ブロツク）はそれぞれDA
Gによつて表現されることができるけれども、それはフ
ローグラフではない。
「生きている変数の解析」は、名前が後に計算に使われ
るかもしれない値を有するか否かを確定する技術を称す
る。この名前が基本ブロツク内で再定義される前に使わ
れるか、又は、この基本ブロツクから「生きて」出てき
て該基本ブロツク内で「再定義」されないかのいずれか
の場合、その名前はブロツクに「生きて」入ると考えら
れる。したがつて、レジスタである値が計算され、基本
ブロツク内で多分使用された後、その値が基本ブロツク
の終わりで「死んで」いるならば、その値を記録する必
要はない。また、全レジスタが満杯で、かつ他のレジス
タが必要とされるならば、「死んでいる」値を現在含む
レジスタに割り当てがなされ得る。
概念的に、第１のコンパイラ変換は、原始コードのスト
リングをフローグラフに写像することからなる。フロー
グラフの節点のそれぞれは基本ブロツクで、かつフロー
グラフの制御とデータパスの関係は、フローグラフの有
向辺によつて定義される。資源の割り付け及び割り当て
の最適化は、まず局所ブロツクレベル、すなわち基本ブ
ロツクレベルで考慮され、次に、大域グラフレベルすな
わちフローグラフレベルで考慮されることができる。
局所最適化では、各基本ブロツクは別々の単位として扱
われ、その内容と無関係に最適化される。データ依存グ
ラフは、基本ブロツクのために形成され、変形され、そ
して、最終機械コードを生成するのに用いられる。その
後、該グラフは放棄され、次の基本ブロツクが考慮され
る。「データ依存グラフ」とは、基本ブロツク内のグラ
フ論理的属性の表現である。基本ブロツクは閉路を含む
ことができないので、全てのデータ依存グラフの基本ブ
ロツクは、DAGによつて表現されることができる。因にD
AGは必ずしも木ではない。実例として、基本ブロツクが
２つの計算文ｘ＝ｕ＋ｖ、ｙ＝ｕ＋ｗから成るならば、
DAGは、閉路がないけれども、木ではない。最後に、大
域最適化は、フローグラフの大域再配置を行ない、基本
ブロツクの境界に文脈情報を提供する。
コンピュータはメモリを含み、その最高速の形態が、最
も高価である。有限個の物理レジスタは、計算及び制御
のために直接使用するオペランドを記憶する。レジスタ
間で演算をコンピユータの命令は、最高速で実行され
る。レジスタが使用できない場合は、中間結果は、プロ
グラム及びデータの大部分が記録されているメインメモ
リにロードされるか、又は、レジスタが使用可能である
場合、前記メインメモリからレジスタにロードされるか
のいずれかでなければならない。メモリからレジスタへ
のロード及びストアは、実質的に長い時間を有する。し
たがつて、フローグラム又は基本ブロツクのいずれかを
評価する場合、１つの目的は、多数の計算名又は計算変
数をレジスタに保持するか、又は必要とされるレジスタ
を使用可能にすることにある。
レジスタの割り付けは、レジスタ（すなわち、必要とさ
れるレジスタ数に常駐すべきソフトウエアストリームの
名前）を伴う一方、割り当てとは、基礎をなすスキー
ム、規則又はモデルに従う節点にレジスタを割り当てる
ステツプである。従来、使用される割り付け方法に中に
は、割り当てを固定することがあつた。すなわち、オブ
ジエクトプログラム量の特定の種類は、一定のレジスタ
に割り当てられた。例えば、サブルーチンリンクは第１
のレジスタ群に、ベースアドレスは第２のレジスタ群
に、算術計算は、第３のレジスタ群に、実行時のスタツ
クポイントは一定のレジスタなどに割り当てることがで
きた。このような固定写像の欠点は、レジスタの使用が
実行要求に動的に従わないことである。これは、幾つか
のレジスタが、全く使用されなかつたり、過剰使用され
たり、又は過少に使用されたりすることを意味する。
大域レジスタ割り付けは、ほとんどプログラムがその時
間のほとんどを内側のループで費すという観測に関係す
る。したがつて、割り当ての１つ方法には、頻繁に使用
される名前を、ループの間中、固定レジスタに保持して
おくことである。したがつて、１つの方法は、一定数の
レジスタを割り当て、各内側のループの最活性名を保持
することである。選択された名前は、異なるループでは
異なる。他の非専用レジスタは、１つのブロツクに対し
て局所的である値を保持するのに使用される。この割り
付け及び割り当ては、いかなる所定のレジスタ数も、大
域レジスタ割り付けに使用可能にするために普遍的な正
しい数ではないという欠点がある。
Chaitin等による“Relister Allocation Via Colorin
g",Computer Languages,Vol.6,1981,pp.47−57,Pergamo
n Press Limited及びChaitinによる“Register Allocat
ion and Spilling Via GraphColoring",Proceeding SIG
NPLAN82,Symposium onCompiler Construction,SIGPLAN
Notices,1982,pp.98−105には、全手続きにわたり大域
レジスタ割り付け方法が記載されている。前記文献で
は、１つを除いて全レジスタは一様なプールの一部であ
ると考えられ、全計算は、これらのレジスタのために同
一の根拠で競合する。実際、いかなるレジスタの部分集
合も保有されない。
前記文献では、メモリよりもむしろレジスタで、できる
だけ多くの計算を保持することが意図されている。なぜ
なら、ロード及びストア命令は、レジスタ−レジスタの
命令よりも高価だからである。また、前記文献には、無
限数のレジスタ（すなわちプールとみなされる。これ
は、中間言語で、プログラムのロード及びストアの数を
最小限にするために許される）を利用することは、コー
ド生成及び最適化の責任であると記載されている。
前記文献の批評的な観察によれば、レジスタの割り付け
は、グラフ彩色問題として解析可能である。グラフ彩色
とは、２つの節点が隣接されているならば（グラフの辺
によつて連結される）それらは異なる色を有するように
その節の各々に色を割り当てることをいう。グラフの
「彩色数」とはその任意の彩色における最少彩色数をい
う。前記文献には、レジスタ割り付けは「レジスタ干渉
グラフ」と呼ばれる構造を利用している。マシン・レジ
スタに常駐する計算又は名前は、それらがプログラムの
任意の点で同時に「生きて」いるならば、互いに「干渉
する」といわれる。
前記文献のグラフ彩色方法は、次のテツプを含んでい
る。（ａ）コードの特定のテキスト配列に対して、名前
から干渉グラフを形成する（ｂ）該グラフの彩色数を確
定し、該彩色数が使用可能なレジスタ数を越えなけれ
ば、彩色（節点にレジスタを割り当てる）して、そうで
ない場合は、最大入出次数を有する節、すなわち節点及
びその連結辺を削除することにより、このグラフを削減
する。（ｃ）値が収束するまで、ステツプ（ｂ）を繰り
返す。（ｄ）コンパイルされたコードストリームに、適
当なメモリへの書込み及びメモリからのロードを埋め込
むことによつて、「こぼれ（spills）」の報告及び管理
を行う。
本発明の目的は、スカラプロセツサ又はベクトルプロセ
ツサのいずれかで、原始コードを実行可能なコードにコ
ンパイルする際に、最適なレジスタの割り付け及び割り
当てを行い、それによつてこぼれ数（メモリへの参照数
及びメモリからの参照数）を最少にすることにある。関
連する目的は、こぼれコード量が基本ブロツク内のテキ
スト配列に対して不変であるように、レジスタを割り付
け及び割り当てることにある。
C.問題点を解決するための手段 スカラプロセツサ又はベクトルプロセツサのいずれかで
原始コードを実行可能コードにコンパイルする際の最適
化フエーズ中、レジスタを割り付け、かつ「基本ブロツ
ク」と呼ばれる分岐のないコード領域に局所的に前記割
り付けを最適化する方法によつて、前記目的は達成され
る。各基本ブロツクは、計算を定義する文を有する。ま
た、各プロセツサは、実行可能コード及びデータ列を記
憶するメモリと、前記メモリをアクセスし、かつアクセ
スされたコードを実行する手段とを含む。このプロセツ
サでは、メモリは、有限のＰ個のレジスタとそれと同等
の無限の内部メモリとを含む２レベルメモリ・モデルと
して写像される。関連することだが、レジスタのアクセ
ス時間は、内部メモリのアクセス時間よりも速い。
本発明の方法は、プロセツサで実現される次の（ａ），
（ｂ）のステツプを含む。（ａ）基本ブロツクのデータ
依存グラフの属性を確定する。（ｂ）２レベルメモリ・
モデルを使用する確定データ依存グラフに「２色の小石
ゲーム」発見法を実行することにより、基本ブロツク内
の全計算に関して、ｐ個のレジスタのうちｑ個の割り付
け及び割り当てを生成する。
上記（ａ），（ｂ）に加えて、（ｃ）生きている変数の
解析を行い、それに応じてループが最も重要な最適化エ
ンテイテイーであると仮定する大域レジスタ割り付け及
び割り当てを生成するステツプを含んでいる局所レジス
タ及び大域レジスタの最適化のための方法によつて、前
述の目的は一層よく達成される。
前記文献の「レジスタ干渉グラフ」と異なり、データ依
存グラフはテキスト配列に対して不変である。本発明の
方法は、割り付け処理を２つのステツプに分割する。第
１のステツプは、有効な局所的割り付けを得ることであ
る。第２のステツプは、局所的割り付けを用いて大域的
割り付けを得ることである。データ依存グラフで行われ
る小石ゲーム発見法は、基本ブロツク内のこぼれが最少
にされることを保証する。該発見法は、基本ブロツクに
対応するグラフ上で赤と青の小石ゲームを行うことを意
味する。メモリへのアクセスは、該グラフ上に青い小石
を置くことによつてモデル化され、一方、レジスタへの
アクセスは、該グラフ上に赤い小石を置くことによつて
モデル化される。このモデルは、こぼれを正確に制御す
る。同じデータ依存グラフは同じ割り付けを生じる。
重要なことは、局所的割り付けを実行する間、使用可能
レジスタの全てが使用されるわけではないことである。
実際、幾つかのレジスタは、大域情報を伝送するために
取つて置かれる。関連することだか、２番目の大きなス
テツプは、これらのレジスタを使用してメモリへのアク
セスをさらに減少させる大域最適化を行うステツプであ
る。これらの大域レジスタのために選ばれる変数は、全
プログラムのロード操作数又はストア操作数を最大限に
減少させるように選択される。
本発明のために、小石ゲームは、DAGで行われる１人用
のゲームである。プレヤーには、２つの種類の赤と青の
小石が与えられる。青い小石の数は無限である一方、赤
い小石の数は、ある数、例えばｐ、に制限さている。最
初、DAGに全てのソースに青の小石を置いている。プレ
ヤーには、以下の動きの何れかをすることが許される。
（１）青い小石の隣りに赤い小石を置く。
（２）赤い小石の隣りに青い小石を置く。
（３）ある節点に赤い小石を置く。ただしすべての先行
節に赤い小石が置かれている場合に限る。
（４）ある節点に、赤い小石を先行節の１つからスライ
ドさせる。ただし、このスライド前に先行節の赤い小石
が置かれていた場合に限る。
（５）任意の時間に赤い小石を取り除く。
これに関連して、青い小石はメモリ位置で、赤い小石は
レジスタである。この意味で、規則（１）はメモリから
のロード、規則（２）はメモリへの書込み、規則（３）
は値の計算を新たなレジスタへにストアすること、規則
（４）は、計算に使用されたオペランドを以前保持して
いたレジスタに前期値の計算をストアすることに相当す
る。レジスタ割り付けの状況におけるゲームの目的は、
こぼれ数を最少にすることである。ここで、こぼれは規
則（１）又は（２）の使用を伴う。
小石ゲームは、Pippengerによつて、“Pebbling"5th I
BM Symposium on the Machematical Foundations of C
omputerSciece,1980年５月26〜28日、箱根、日本におい
て述べられている。この論文では、小石ゲームがコンパ
イラ、特にコード生成と最適化を含む応用範囲を見付け
たことを指摘している。この論文で述べられているのは
１色のゲームであり、「黒色小石ゲーム」と呼ばれるこ
ともある。
実を言えば、「黒色小石ゲーム」は、時間−空間トレー
ドオフの研究に用いられてきた。「時間−空間トレード
オフ」は、使用可能レジスタ数と計算を実行するのに要
する時間との積によつて形成される係数の変更の結果を
含む。この積は、データ依存グラフの節点数に比例する
量である。もし１色だけがレシスタを表現するならば、
所定の計算の場合、「前記計算を実行するのに必要とさ
れるレジストの最低数はいくつ？」という問いかけが従
来なされてきた。しかしながら、前記１色小石ゲーム
は、本発明の方法を教示も示唆もしない。重要なこと
は、本発明が、２色小石ゲームにより、DAG上でレジス
タの割り付け及び割り当てを扱い、それによつて、通常
のグラフ配色方法に比べ、こぼれを共に最少にする局所
最適化及びループに基づいた大域最適化を行うことであ
る。
D.実施例 まず、小石ゲーム発見法アルゴリズムを記述して、局所
最適化を達成するレジスタの割り付け及び割り当てにつ
いて説明する。続いて、大域割り付けを説明する。
局所最適化 局所最適化は「小石ゲーム」発見法を利用する。本発明
のために、「発見法」は、上来、最適な結果を達成する
ために直観に基づいたマシンで実現可能な手続き又はア
ルゴリズムである。
第１例 第１図〜第６図には、基本ブロツクに分割され、かつDA
Gタイプ対応のデータ依存グラフによつて表現される計
算シーケンスが示されている。第１の近似への発見法
は、以下のようにして進行する。
1.DAGを調査し、ｐ個の支配節、すなわち、最大後続節
数を識別する。ここで、ｐは赤い小石の数である。この
ようなｐ個の節点の集合毎に、赤でない集合の節点数で
あるコストを関連させる。次に、これらの集合の中か
ら、最少の支配節のコスト／サイズの値を有する集合を
選ぶ。これは、計算のために「有望な」領域を規定す
る。
2.次に、上記選択された集合の直接後続節である節点毎
のカバーコストを計算することにより、「有効な」計算
を見つける。カバーコストは２つのパラメータを有す
る。これらは、（ａ）赤い小石が置かれていない先行節
の数、（ｂ）この節点の直接行節の最少スライドコスト
を含む。関連して、このスライドコストは、最少の出次
数を有する（ａ）の先行節を参照する。出次数によつ
て、このスライドはまた計算されていない後続節を意味
する。因に一旦計算が実行されると、計算されていない
後続節数は変化する。したがつて、例えば基本ブロツク
１を説明する第２図では、節点t1はカバーコスト（２、
１）を有する。ここで、先行節数は２である（節x,
y）。一方、スライドコスト（計算されていない後続節
に対する出次数）は、最初、ｘに対して１、ｙに対して
３である。スライドコストがより小さいものが選択され
る。一旦カバーコストが計算されると、アルゴリズムの
次のステツプで実行される計算は、最小のカバーコスト
を有するように選ばれる。
3.一旦、「有効」計算を決定すると、赤い小石を置く従
属節は、小石をスライデイングをするための規則を使用
する。いかなる赤い小石もスライドを実行するのに使用
されることができない場合、DAG上に現在ない小石が、
存在すれば用いられる。
4.レジスタが使用できないならば、中間又は最終結果は
メモリに書き込まれ、かつ、必要な場合、使用可能なレ
ジスタにロードし直さなければならない。
次に、第２図を参照すると、節点t1は節点ｘおよびｙに
依存している一方、節点ｑは節点ｙ及びｚに依存してい
る。この結果ｖは接点t1に及びｙに依存する。３つのレ
ジスタr0,r1,r2が使用可能であると仮定すると、３つを
節点からなる支配節が選ばれる。唯一の可能な支配節
は、集合（x,y,z）である。したがつて、これは「有望
な」集合と呼ばれる。
節点t1及びｑは、選択された支配集合の後続節である。
各節点毎に、カバーコストが計算される。節点t1のカバ
ーコストは（2,1）である。その理由は、節点t1の２つ
の先行節には小石が置かれていなく、かつ、ｘの計算さ
れていない後続節は１つだけなので、最少スライドコス
トは１であることによる。このことは節点ｑの場合も同
様である。節点１、節点ｑの両方のカバーコストはどち
らも同じなので、１つの節点（例えば節点t1）が任意に
選ばれる。節点t1を計算するためには、まず、赤い小石
は節点ｘ及びｙに置かなければならない。次に、節点ｘ
のスライドコストが１であるため、節点ｘを節点t1にス
ライドさせる。いま、節点ｖは節点t1の赤い小石を節点
ｙにスライドさせることで計算されることができる。続
いて、節点ｑは、節点ｚにロードした後、節点ｙの小石
を節点ｑにスライドさせることで計算されることができ
る。
前述の解析は、十分な数のレジスタが与えられると、ス
ケジユーリングは合理的にスムーズに行えることを指摘
している。
次に、第３図及び第４図を参照する。この第３図及び第
４図には、第１図に示した計算シーケンスの前記文献に
よる従来のレジスタ干渉グラフが示されている。第３図
のグラフは、技術的に３色で彩色可能である。しかしな
がら、２つのレジスタ（r0,r1）のみが使用可能なら
ば、グラフの彩色は本質的に可能でない。最高次数の節
点を除去させることが可能になるであろう。この点につ
いて、第４図は、節点ｘ及びｙが除去された従来の干渉
グラフの例である。しかしながら、２色で彩色を可能に
するためには、節点ｚもまた除去されなければならな
い。３つの節点を除去させることは、こぼれコードの実
質量を示す。対照的に、２つのレジスタのみが使用可能
にされ、かつ、第２のデータ依存グラフにより割り当て
られるならば、比べると３つのロード及び１つのストア
のみが必要とされる。
改良例 次に、第５図及び第６図を参照する。再び、３つのレジ
スタと３つの赤い小石が使用可能であると仮定する。ア
ルゴリズムによると、節点u,v及びｗは、支配節として
選ばれる。カバーコスト（ｘ）＝（2,1）であり、一方
カバーコスト（ｙ）＝（2,2）である。したがつてこの
アルゴリズムは、節点ｘを評価するために選択する。カ
バーコスト＝（c1,C2）であるので、c1＝２の場合、こ
のアルゴリズムは、現境界に対するこぼれ節点（ｘ）を
計算する。この境界という用語は、集合のあらゆる節点
ｖに対して、この節点か小石を有しており、かつ節点ｖ
の少なくとも１つの後続節が計算されていない性質を有
する節点の集合から得られる。これが境界と呼ばれてい
る。
DAG上にいかなる赤い小石も置かれていないので、空で
ある。したがつて、この方法によれば、節点ｕ及びｖに
自由に赤い小石を置くことができる。また、c2＝１なの
で、節点ｕにおけるレジスタは節点ｘにスライドされ、
１つの計算が終了される。もう１度、他の支配節が選択
される。カバーコスト（ｐ）＝（0,1）であるため、今
度は、節点ｐが計算のために目標とされる。前述のよう
に、c2＝１である。これは、節点ｘ上のレジスタが節点
ｐにスライドされることを意味する。
いかなる他の選択も使用可能でないため、この方法は節
点ｙ、続いて節点計算しなければならないことが明から
である。第５図を参照する。３つのロードのみが実行さ
れ、かつ節点ｐ及びｚがレジスタで使用可能であること
を注意すべきである。これは、いずれかが後に使用され
るならば、メモリからのロードを行なう必要が全くない
ことを意味する。
重要なことは、シーケンスコードがどんなに並べ変えら
れても、データ依存グラフは不変である。したがつて、
この方法により生じる結果は、テキスト順序に依存しな
い。
また、従来の彩色が第６図に示されるようなコードに適
用されたならば、ロード数は４であり、一方本発明の方
法の場合、ロード数は、最小限の３のみであることを注
意すべきである。
大域最適化 本発明では、大域最適化は、まず、使用可能なレジスタ
の全数のある一部を用いて、フローグラフに現われる順
序で、各基本ブロツク毎に局所的割り付けを実行するこ
とを含む。次に、ループが最も決定的なエンテイテイー
であると仮定し、残りのレジスタを使用して大域情報を
伝える。
第７図には、開始節で初期設定され、かつ終了節で終了
するフローグラフが示されている。
局所的割り付けなされたと仮定すると、大域ステツプ
は、各局所的割り付けでロードされ、かつストアされる
変数の集合を調査する。これらの変数に対して、変数の
ロード又はストアの回数の係数が行なわれる。この計数
は、いわゆる変数のネステイングレベルによつてバイア
スされる。このネステイングレベルは、該変数を取り囲
むフローグラフのループ数を参照する。このリストか
ら、最高値を有する変数が大域レジスタに常駐するよう
に選択される。この処理は、使用可能な大域レジスタが
なくなるか又は、このリストが空になるまで、繰り返さ
れる。
この大域的割り付け方法は、いくつかの変形を有する。
例えば、大域レジスタに入れられる変数は、局所的割り
付けに対応するフローグラフの最大の生きている範囲を
表わすものである。すなわち、局所的割り付けは、入力
プログラムの対応する基本ブロツクと取り換えられる。
続いて、基本ブロツクに局所的でない全ての変数に対し
て、生きている範囲が計算される。生きている範囲は、
使用回数及びネステイングレベル・ブレイキングタイを
有する大域レジスタに割り当てられるのはどの変数であ
るかを決定するのに使用される。つまり、基本ブロツク
に局所的でない変数であつて、最大の生きている範囲を
有する変数が大域レジスタに割り当てられるのである。
そして、２つ以上の変数が同じ生きている範囲を有する
場合は、使用回数又はネステイングレベルが最大である
変数に、大域レジスタの１つが指定されるのである。
ループの底で、変数が異なるレジスタで終わる場合に
は、これらがループの先頭にあると想定されるので、い
かなる転送も必要なく、又は、転送数がある所定のしき
い値以下であるまで、該ループを展開することが可能で
ある。
下記表は、局所レジスタの割り付けに使用する小石ゲー
ム発見法のアルゴリズムを詳述したものである。
Algorithm Local_Alloc（DAG,num_registers）current_
frontier:＝sources（Ｄ）:/＊set frontier to source
s of DAG＊／ current_configuration:＝（empty,current_frontie
r）； while（number of uncomputed nodes not zero）do Find a est S,of p nodes, in the current frontier,s
uch that move_cost（Ｓ）／（number of nodes that S
dominates）in minimized. ／＊find a good computation to do＊/compute the co
ver cost of every node if FS（Ｓ）； Let u be the node in FS（Ｓ） with the smallest co
ver cost,where cover_cost（ｕ）＝（c1,c2）； ／＊find the possible spill nodes for the computat
ion＊／ if c1＞0 then for each node v in spill_nodes（u,
S）,if v is not pebbled blue then place a blue peb
ble on v.Remove the red pebble from v. while not all predecessors of u are pebbled red do put a free red pebble on a predecessor of u not pe
bled red. ／＊pebble the computation＊／ if c2＝1 then slide the node with slide_cost＝1 to
u else ie any free red pebbles, then put free pelle on u else begin let v be the predecessor of u with the smallest sl
ide cost. if slide_cost（ｖ）＞0,put a blue pebble on v; slide v to u; end; od; 本発明の拡張 本発明の方法は、IBM（登録商標）システム/370タイプ
のスカラプロセツサ、又は、IBM3090によつて代表され
るようなベクトルマシンで使用されることができる。ベ
クトルプロセツサでは、最高速度で計算を実行すること
が望まれる。これは、計算がメモリをアクセスする頻度
をできるだけ少なくすべきであることを意味する。なぜ
なら、ベクトルレジスタへのアクセスに比べると、メモ
リ・アクセスは非常に遅いからである。前述のように、
小石ゲームの発見法は、次のようにしてベクトルレジス
タの数を決定するのに使うことができる。まず、ベクト
ルレジスタの開始番号を選択する。続いて、実行される
べきベクトル計算に対応するデータ依存グラフDAGに該
発見法を実行する。次に、この一定数のレジスタのため
に実行されるロード／ストアの数を計算する。この後、
この数と、必要とされるアクセス数（すなわち、ソース
数とシンク数の和）の下限と比較する。あまり多くのア
クセス数が実行されるならば、レジスタ数を倍にしてア
ルゴリズムを再適用する。下限に達したならば、レジス
タ数を半分にして、最適レジスタ数が識別されるまで、
アルゴリズムを繰り返す。これは、ベクトルレジスタ数
について二分探索を行ない、探索パラメータを決定する
のに小石ゲーム発見法を用いることと等価である。
本発明の他の拡張は、計算をメモリへのロード及びスト
アとオーバーラツプされるマシンでの使用である。該発
見法は、現在レジスタにあるデータに基づいて、できる
だけ多くの計算を試みるので、計算とメモリアクセスと
の間の有効なオーバーラツプを提供すべきである。
処理環境 本発明は、PL/I,FORTRAN,COBOL等の高級言語コンパイラ
のオプテイマイザ部に埋め込まれ、かつ、IBMシステム/
370等のシステム上で、米国特許第3400371号明細書およ
びIBM System/370 Principles of Operation,IBM Publi
cation GA22−7000−６に記載されているように実行す
ると、簡便に実行できる。
E.発明の効果 本発明によれば、コンパイル時に最適なレジスタの割り
付けを行うことができ、メモリへのアクセスを最小限に
抑えることができる。
【図面の簡単な説明】
第１図は、３つの基本ブロツクの計算シーケンスを示す
図である。 第２図は、本発明により、小石ゲーム発見法を用いる局
所的レジスタ割り付けを説明する第１の例で用いられた
第１のブロツクのデータ依存グラフへの表現を示す図で
ある。 第３図は、従来技術による第１図のシーケンスのレジス
タ干渉グラフを示す図である。 第４図は、従来技術による彩色を可能とするようにいく
つかの節点を除去した第３図の干渉グラフを示す図であ
る。 第５及び第６図は、本発明により、小石ゲーム発見法を
用いる局所的レジスタ割り付けの第２例で使用された計
算例、データ依存グラフ及びレジスタ活動シーケンスを
示す。 第７図は、本発明による大域的割り付けのステツプの記
述に関係するフローグラフの説明図である。

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】有限数ｐ個のレジスタと、このレジスタの
    総容量に比べて十分大きい記憶容量を有し、前記レジス
    タよりアクセス時間の遅い内部メモリとを備えたプロセ
    ッサで実行可能な目的コードを生成するように原始コー
    ドをコンパイルする際に、計算を定義する連続した文の
    列からなり、分岐しないコード領域を含む各基本ブロッ
    クへのレジスタの割り付けを最適化するようにしたコン
    パイル方法において、 前記基本ブロックのデータ依存関係を閉路のない有向グ
    ラフで表現したデータ依存グラフを形成し、 前記形成されたデータ依存グラフに対して２色小石ゲー
    ム発見法を実行することによって前記ｐ個のレジスタの
    うちのｑ個（ここで０＜ｑ＜ｐである）に局所レジスタ
    を割り付け、 前記各基本ブロックのフローグラフで生きている変数の
    解析を実行し、かつ前記基本ブロック間の前記フローグ
    ラフのループが最も重要な最適化エンティティであると
    仮定する残りのレジスタ（ｐ−ｑ）個に大域レジスタを
    割り付けし、 使用可能なレジスタと同数を節を、前記データ依存グラ
    フの節の中から後続節の数が多いものの順に選択し、選
    択された前記集合の直接後続節である全ての節点のカバ
    ーコストを計算し、かつ前記カバーコストが最小である
    前記集合の直接後続節にレジスタを割り当て、使用可能
    で割り付け可能なレジスタがない場合、計算で得られた
    中間結果又は最終結果を前記内部メモリに書き込み、必
    要な場合、その後使用可能なレジスタに前記結果をロー
    ドし直すことを含み、 前記大域レジスタの割り付けは、基本ブロックに局所的
    でない全ての変数に対して生きている範囲を定め、最大
    の生きている範囲を有する変数を大域レジスタに割り付
    け、同一の生きている範囲を有する２以上の変数の場
    合、最大の使用回数を有する変数に前記（ｐ−ｑ）個の
    レジスタの１つを割り当てることを含むことを特徴とす
    るコンパイル方法。
JP61266812A 1985-12-17 1986-11-11 コンパイル方法 Expired - Lifetime JPH0776927B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US809989 1985-12-17
US06/809,989 US4782444A (en) 1985-12-17 1985-12-17 Compilation using two-colored pebbling register allocation method such that spill code amount is invariant with basic block's textual ordering

Publications (2)

Publication Number Publication Date
JPS62144247A JPS62144247A (ja) 1987-06-27
JPH0776927B2 true JPH0776927B2 (ja) 1995-08-16

Family

ID=25202684

Family Applications (1)

Application Number Title Priority Date Filing Date
JP61266812A Expired - Lifetime JPH0776927B2 (ja) 1985-12-17 1986-11-11 コンパイル方法

Country Status (8)

Country Link
US (1) US4782444A (ja)
EP (1) EP0229245A3 (ja)
JP (1) JPH0776927B2 (ja)
KR (1) KR910009116B1 (ja)
CN (1) CN1003679B (ja)
BR (1) BR8605865A (ja)
CA (1) CA1264859A (ja)
ES (1) ES2004348A6 (ja)

Families Citing this family (111)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS6378231A (ja) * 1986-09-22 1988-04-08 Nec Corp 部分的プログラム結合方式
JPS6476322A (en) * 1987-09-18 1989-03-22 Hitachi Ltd Program synthesizing method
JPS6481035A (en) * 1987-09-22 1989-03-27 Nec Corp C compiler
US4953084A (en) * 1987-11-16 1990-08-28 Hewlett-Packard Company Method and apparatus using variable ranges to support symbolic debugging of optimized code
US5121498A (en) * 1988-05-11 1992-06-09 Massachusetts Institute Of Technology Translator for translating source code for selective unrolling of loops in the source code
US5129086A (en) * 1988-11-29 1992-07-07 International Business Machines Corporation System and method for intercommunicating between applications and a database manager
US5070453A (en) * 1989-04-10 1991-12-03 At&T Bell Laboratories System and method for scheduling data transfers among a plurality of data processing units to avoid conflicting data requests
US5193190A (en) * 1989-06-26 1993-03-09 International Business Machines Corporation Partitioning optimizations in an optimizing compiler
US5274820A (en) * 1989-08-14 1993-12-28 International Business Machines Corporation Method and system for eliminating operation codes from intermediate prolog instructions
JPH03150637A (ja) * 1989-11-08 1991-06-27 Oki Electric Ind Co Ltd パイプライン対応のレジスタ割付け方式
US5428793A (en) * 1989-11-13 1995-06-27 Hewlett-Packard Company Method and apparatus for compiling computer programs with interproceduural register allocation
WO1991010954A1 (en) * 1990-01-19 1991-07-25 Alliant Computer Systems Corporation A risc vectorization system
CA2010067C (en) * 1990-02-14 1993-10-26 Steven Murray Hoxey Reducing pipeline delays in compilers by code hoisting
EP0453160A3 (en) * 1990-04-20 1993-09-15 Digital Equipment Corporation A method and apparatus for analyzing the flow of data through a complex information exchange system
US5212794A (en) * 1990-06-01 1993-05-18 Hewlett-Packard Company Method for optimizing computer code to provide more efficient execution on computers having cache memories
US5107418A (en) * 1990-06-11 1992-04-21 Supercomputer Systems Limited Partnership Method for representing scalar data dependences for an optimizing compiler
US5202975A (en) * 1990-06-11 1993-04-13 Supercomputer Systems Limited Partnership Method for optimizing instruction scheduling for a processor having multiple functional resources
JPH0816871B2 (ja) * 1990-12-07 1996-02-21 富士ゼロックス株式会社 プログラム翻訳装置およびプログラム翻訳方法
US5511218A (en) * 1991-02-13 1996-04-23 Hughes Aircraft Company Connectionist architecture for weapons assignment
JP3032031B2 (ja) * 1991-04-05 2000-04-10 株式会社東芝 ループ最適化方法及び装置
JP3049814B2 (ja) * 1991-04-09 2000-06-05 日本電気株式会社 マイクロコンピュータの言語処理装置
US5530866A (en) * 1991-07-30 1996-06-25 Tera Computer Company Register allocation methods having upward pass for determining and propagating variable usage information and downward pass for binding; both passes utilizing interference graphs via coloring
US5339428A (en) * 1991-09-04 1994-08-16 Digital Equipment Corporation Compiler allocating a register to a data item used between a use and store of another data item previously allocated to the register
JP2970785B2 (ja) * 1991-10-18 1999-11-02 松下電器産業 株式会社 資源割り付け装置
US5386562A (en) * 1992-05-13 1995-01-31 Mips Computer Systems, Inc. Circular scheduling method and apparatus for executing computer programs by moving independent instructions out of a loop
US5418958A (en) * 1992-07-15 1995-05-23 Sun Microsystems, Inc. Register allocation by decomposing, re-connecting and coloring hierarchical program regions
US5367651A (en) * 1992-11-30 1994-11-22 Intel Corporation Integrated register allocation, instruction scheduling, instruction reduction and loop unrolling
US5469572A (en) * 1992-12-01 1995-11-21 Taylor; James M. Post compile optimizer for linkable object code
AU5954194A (en) * 1992-12-21 1994-07-19 Apple Computer, Inc. Method and apparatus for transforming an arbitrary topology collection of nodes into an acyclic directed graph
SE502733C2 (sv) * 1993-06-11 1995-12-18 Ellemtel Utvecklings Ab Sätt att undvika ej önskvärd interferens mellan tjänster i ett telekommunikationssystem
CA2643234C (en) * 1993-10-29 2012-05-15 Microsoft Corporation Method and system for generating a computer program
US5491823A (en) * 1994-01-25 1996-02-13 Silicon Graphics, Inc. Loop scheduler
US5966539A (en) * 1994-03-01 1999-10-12 Digital Equipment Corporation Link time optimization with translation to intermediate program and following optimization techniques including program analysis code motion live variable set generation order analysis, dead code elimination and load invariant analysis
US5590356A (en) * 1994-08-23 1996-12-31 Massachusetts Institute Of Technology Mesh parallel computer architecture apparatus and associated methods
JP3606387B2 (ja) * 1994-09-13 2005-01-05 松下電器産業株式会社 コンパイル装置
US5802375A (en) * 1994-11-23 1998-09-01 Cray Research, Inc. Outer loop vectorization
CN1149476C (zh) * 1995-03-16 2004-05-12 松下电器产业株式会社 资源分配装置
US5659754A (en) * 1995-03-31 1997-08-19 Sun Microsystems, Inc. Method and apparatus for an improved optimizing compiler
US5691897A (en) * 1995-05-30 1997-11-25 Roy-G-Biv Corporation Motion control systems
US20100131081A1 (en) * 1995-05-30 2010-05-27 Brown David W Systems and methods for motion control
US7137107B1 (en) 2003-04-29 2006-11-14 Roy-G-Biv Corporation Motion control systems and methods
US7024666B1 (en) * 2002-01-28 2006-04-04 Roy-G-Biv Corporation Motion control systems and methods
US7139843B1 (en) 1995-05-30 2006-11-21 Roy-G-Biv Corporation System and methods for generating and communicating motion data through a distributed network
US20060206219A1 (en) * 1995-05-30 2006-09-14 Brown David W Motion control systems and methods
JP3060907B2 (ja) * 1995-07-28 2000-07-10 日本電気株式会社 言語処理プログラムの処理方式
US5761514A (en) * 1995-08-31 1998-06-02 International Business Machines Corporation Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system
US6135650A (en) * 1995-12-22 2000-10-24 Sun Microsystems, Inc. Method and system for wrapper routine optimization
US5901317A (en) * 1996-03-25 1999-05-04 Sun Microsystems, Inc. Method and system for register allocation using multiple interference graphs
US5946491A (en) * 1996-06-06 1999-08-31 International Business Machines Corporation Register allocation method and apparatus for gernerating spill code as a function of register pressure compared to dual thresholds
US5901316A (en) * 1996-07-01 1999-05-04 Sun Microsystems, Inc. Float register spill cache method, system, and computer program product
KR100186338B1 (ko) * 1996-08-02 1999-05-15 문정환 교환법칙이 성립하는 연산기의 입력단수 저감방법
WO1998006038A1 (en) * 1996-08-07 1998-02-12 Sun Microsystems, Inc. Architectural support for software pipelining of loops
US6049864A (en) * 1996-08-20 2000-04-11 Intel Corporation Method for scheduling a flag generating instruction and a subsequent instruction by executing the flag generating instruction in a microprocessor
US5937195A (en) * 1996-11-27 1999-08-10 Hewlett-Packard Co Global control flow treatment of predicated code
US5890000A (en) * 1996-12-04 1999-03-30 International Business Machines Corporation Cooperation of global and local register allocators for better handling of procedures
US6031994A (en) * 1997-04-01 2000-02-29 Intel Corporation Method for determining the set of variables that may be ambiguously defined at a point in a computer program
US6151704A (en) * 1997-04-01 2000-11-21 Intel Corporation Method for optimizing a loop in a computer program by speculatively removing loads from within the loop
US6029005A (en) * 1997-04-01 2000-02-22 Intel Corporation Method for identifying partial redundancies in a new processor architecture
US6016398A (en) * 1997-04-01 2000-01-18 Intel Corporation Method for using static single assignment to color out artificial register dependencies
US5991540A (en) * 1997-04-01 1999-11-23 Intel Corporation Method for identifying partial redundancies in existing processor architectures
CA2205797C (en) * 1997-05-22 2001-04-24 Andrew Wilfred Macleod A system for local context spilling for graph colouring register allocators
US6139200A (en) * 1997-06-30 2000-10-31 Sun Microsystems, Inc. Register resource allocation feedback
US5987259A (en) * 1997-06-30 1999-11-16 Sun Microsystems, Inc. Functional unit switching for the allocation of registers
US6009272A (en) * 1997-06-30 1999-12-28 Sun Microsystems, Inc. Register allocation via selective spilling
US6314562B1 (en) 1997-09-12 2001-11-06 Microsoft Corporation Method and system for anticipatory optimization of computer programs
US20010032278A1 (en) * 1997-10-07 2001-10-18 Brown Stephen J. Remote generation and distribution of command programs for programmable devices
US6058265A (en) * 1997-10-21 2000-05-02 Hewlett Packard Company Enabling troubleshooting of subroutines with greatest execution time/input data set size relationship
US6292938B1 (en) * 1998-12-02 2001-09-18 International Business Machines Corporation Retargeting optimized code by matching tree patterns in directed acyclic graphs
US6954927B2 (en) * 1999-02-17 2005-10-11 Elbrus International Hardware supported software pipelined loop prologue optimization
US6317876B1 (en) * 1999-06-08 2001-11-13 Hewlett-Packard Company Method and apparatus for determining a maximum number of live registers
JP4041248B2 (ja) * 1999-07-09 2008-01-30 松下電器産業株式会社 コンパイラ装置、コンパイルプログラムが記録されたコンピュータ読み取り可能な記録媒体及びコンパイル方法
US8032605B2 (en) 1999-10-27 2011-10-04 Roy-G-Biv Corporation Generation and distribution of motion commands over a distributed network
US20100131078A1 (en) * 1999-10-27 2010-05-27 Brown David W Event driven motion systems
US6885898B1 (en) 2001-05-18 2005-04-26 Roy-G-Biv Corporation Event driven motion systems
CA2288614C (en) 1999-11-08 2004-05-11 Robert J. Blainey Loop allocation for optimizing compilers
US6725218B1 (en) 2000-04-28 2004-04-20 Cisco Technology, Inc. Computerized database system and method
JP3651774B2 (ja) * 2000-09-12 2005-05-25 インターナショナル・ビジネス・マシーンズ・コーポレーション コンパイラ及びそのレジスタ割付方法
US6912647B1 (en) 2000-09-28 2005-06-28 International Business Machines Corportion Apparatus and method for creating instruction bundles in an explicitly parallel architecture
US6779106B1 (en) 2000-09-28 2004-08-17 International Business Machines Corporation Apparatus and method for an enhanced integer divide in an IA64 architecture
US6886094B1 (en) 2000-09-28 2005-04-26 International Business Machines Corporation Apparatus and method for detecting and handling exceptions
US6799262B1 (en) 2000-09-28 2004-09-28 International Business Machines Corporation Apparatus and method for creating instruction groups for explicity parallel architectures
US6883165B1 (en) 2000-09-28 2005-04-19 International Business Machines Corporation Apparatus and method for avoiding deadlocks in a multithreaded environment
US7904194B2 (en) 2001-02-09 2011-03-08 Roy-G-Biv Corporation Event management systems and methods for motion control systems
WO2002071241A1 (en) 2001-02-09 2002-09-12 Roy-G-Biv Corporation Event management systems and methods for the distribution of motion control commands
US7013460B2 (en) * 2001-05-15 2006-03-14 Hewlett-Packard Development Company, L.P. Specifying an invariant property (range of addresses) in the annotation in source code of the computer program
US20030079210A1 (en) * 2001-10-19 2003-04-24 Peter Markstein Integrated register allocator in a compiler
US7263694B2 (en) * 2001-10-26 2007-08-28 International Business Machines Corporation Directed non-cyclic graph walking system for data processing and analysis in software application
US20030237080A1 (en) * 2002-06-19 2003-12-25 Carol Thompson System and method for improved register allocation in an optimizing compiler
US7069548B2 (en) * 2002-06-28 2006-06-27 Intel Corporation Inter-procedure global register allocation method
US20040025151A1 (en) * 2002-07-31 2004-02-05 Shan-Chyun Ku Method for improving instruction selection efficiency in a DSP/RISC compiler
US7111287B2 (en) * 2003-01-10 2006-09-19 International Business Machines Corporation Global processor resource assignment in an assembler
US7185329B1 (en) * 2003-03-28 2007-02-27 Applied Micro Circuits Corporation Use of different color sequences for variables of different sizes and different semantics
US7207032B1 (en) * 2003-03-28 2007-04-17 Applied Micro Circuits Corporation Expanding a software program by insertion of statements
US20060064503A1 (en) 2003-09-25 2006-03-23 Brown David W Data routing systems and methods
US8027349B2 (en) * 2003-09-25 2011-09-27 Roy-G-Biv Corporation Database event driven motion systems
US20100131077A1 (en) * 2004-02-25 2010-05-27 Brown David W Data Collection Systems and Methods for Motion Control
US7469404B2 (en) * 2004-06-30 2008-12-23 Intel Corporation Bank assignment for partitioned register banks
KR100597414B1 (ko) * 2004-10-21 2006-07-05 삼성전자주식회사 데이터 처리 장치 및 이를 이용한 레지스터 할당 방법
CN100337202C (zh) * 2004-12-03 2007-09-12 中国科学院计算技术研究所 一种汇编代码热函数中的热路径搜寻方法
US20060200811A1 (en) * 2005-03-07 2006-09-07 Cheng Stephen M Method of generating optimised stack code
CN100414505C (zh) * 2005-07-08 2008-08-27 中国科学院计算技术研究所 一种基于组合并算法的偏移量分配优化方法
US7797692B1 (en) * 2006-05-12 2010-09-14 Google Inc. Estimating a dominant resource used by a computer program
US8237726B2 (en) * 2009-06-26 2012-08-07 Intel Corporation Register allocation for message sends in graphics processing pipelines
US8933954B2 (en) 2011-03-23 2015-01-13 Qualcomm Incorporated Register allocation for graphics processing
CN103399741B (zh) * 2013-07-24 2016-05-25 中国科学院声学研究所 一种汇编级静态路径剖析方法及装置
US9619214B2 (en) 2014-08-13 2017-04-11 International Business Machines Corporation Compiler optimizations for vector instructions
US10169014B2 (en) 2014-12-19 2019-01-01 International Business Machines Corporation Compiler method for generating instructions for vector operations in a multi-endian instruction set
US9588746B2 (en) 2014-12-19 2017-03-07 International Business Machines Corporation Compiler method for generating instructions for vector operations on a multi-endian processor
US9569190B1 (en) 2015-08-04 2017-02-14 International Business Machines Corporation Compiling source code to reduce run-time execution of vector element reverse operations
US9880821B2 (en) 2015-08-17 2018-01-30 International Business Machines Corporation Compiler optimizations for vector operations that are reformatting-resistant
KR20170047957A (ko) * 2015-10-26 2017-05-08 삼성전자주식회사 반도체 장치의 동작 방법 및 반도체 시스템

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE1250659B (de) * 1964-04-06 1967-09-21 International Business Machines Corporation, Armonk, NY (V St A) Mikroprogrammgesteuerte Datenverarbeitungsanlage
US3921153A (en) * 1973-08-02 1975-11-18 Ibm System and method for evaluating paging behavior
US4493020A (en) * 1980-05-06 1985-01-08 Burroughs Corporation Microprogrammed digital data processor employing microinstruction tasking and dynamic register allocation
US4378590A (en) * 1980-09-03 1983-03-29 Burroughs Corporation Register allocation apparatus
US4435753A (en) * 1980-10-31 1984-03-06 International Business Machines Corporation Register allocation system using recursive queuing during source code compilation
US4571678A (en) * 1982-11-05 1986-02-18 International Business Machines Corporation Register allocation and spilling via graph coloring
US4567574A (en) * 1983-03-14 1986-01-28 International Business Machines Corporation Optimizing cobol object code instruction path length with respect to perform statements
JPS6140643A (ja) * 1984-07-31 1986-02-26 Hitachi Ltd システムの資源割当て制御方式
US4656583A (en) * 1984-08-13 1987-04-07 International Business Machines Corporation Method for improving global common subexpression elimination and code motion in an optimizing compiler
US4667290A (en) * 1984-09-10 1987-05-19 501 Philon, Inc. Compilers using a universal intermediate language
US4656582A (en) * 1985-02-04 1987-04-07 International Business Machines Corporation Generating storage reference instructions in an optimizing compiler
US4722071A (en) * 1985-04-19 1988-01-26 Pertron Controls, Corporation Compiler for evaluating Boolean expressions

Also Published As

Publication number Publication date
CN1003679B (zh) 1989-03-22
EP0229245A2 (en) 1987-07-22
CA1264859A (en) 1990-01-23
KR910009116B1 (ko) 1991-10-31
EP0229245A3 (en) 1990-03-21
KR870006460A (ko) 1987-07-11
ES2004348A6 (es) 1989-01-01
US4782444A (en) 1988-11-01
JPS62144247A (ja) 1987-06-27
BR8605865A (pt) 1987-08-25
CN86107764A (zh) 1987-07-01

Similar Documents

Publication Publication Date Title
US4782444A (en) Compilation using two-colored pebbling register allocation method such that spill code amount is invariant with basic block's textual ordering
Dehnert et al. Compiling for the Cydra
Chow et al. The priority-based coloring approach to register allocation
Click Global code motion/global value numbering
US6446258B1 (en) Interactive instruction scheduling and block ordering
Kieburtz The G-machine: A fast, graph-reduction evaluator
JPH04225431A (ja) 命令キャッシュ効率を増大するコンピュータ命令をコンパイルする方法
Rawat et al. Associative instruction reordering to alleviate register pressure
Cierniak et al. Just‐in‐time optimizations for high‐performance Java programs
CN112130848B (zh) 一种面向便笺式存储器的带宽感知循环分块优化方法、编译系统、设备及存储介质
Tang et al. Heap analysis and optimizations for threaded programs
Gheorghioiu Statistically determining memory consumption of real-time java threads
Ekanadham Future scientific programming on parallel machines
Gupta et al. Compile-time techniques for improving scalar access performance in parallel memories
Lang Improved stack allocation using escape analysis in the KESO multi-JVM
CN121478289A (zh) 一种动态稀疏计算编译优化方法
Muller et al. Caches with compositional performance
Williams et al. Genetic compilers: A new technique for automatic parallelisation
Anderson et al. Implementing and optimizing Lisp for the Cray
Ju et al. Develop and prototype code generation techniques for a clause-based GPU
Cooper et al. Compiler-Based Code-Improvement Techniques
JPH03135630A (ja) 命令スケジューリング方式
Maurer An SSA-based register allocator for the Glasgow Haskell compiler
CN120780309A (zh) 面向图计算统一编程模型的编译方法及系统
Sampaio GPU Divergence: Analysis and Register Allocation