冗長な符号拡張命令の除去手法

書誌事項

タイトル別名
  • ジョウチョウ ナ フゴウ カクチョウ メイレイ ノ ジョキョ シュホウ
  • A Method for Elimination of Redundant Sign Extensions

この論文をさがす

抄録

近年,64ビットアーキテクチャが使われ始め,32ビットアーキテクチャから移行が行われようとしている.しかし,32ビットアーキテクチャを前提として設計されたプログラムは,多くのデータサイズが32ビットとして扱われている.たとえばJava言語は,最も多く使われるint型を32ビットと規定している.このようなプログラムを64ビットアーキテクチャ上で実行させるには,多くの整数型命令に対して32ビットから64ビットへの符号拡張を行う命令が必要となり,プログラムの実行速度を下げる.我々は,符号拡張命令をできるだけ除去するために,最初にデータフロー解析を使った実装を行った.しかし,この手法では配列インデックスのアドレス計算に対する符号拡張命令は,ほとんどの場合除去できず,さらにプログラム上でより多く実行される場所から選択的に除去するということができなかった.そこで,我々は効果的に符号拡張命令の除去と移動を行う新しいアルゴリズムを提案する.本稿では,特にJava言語に対する実装手法について述べているが,他の言語でも実装可能である.我々の手法は,より多く実行される場所から順に,変数の依存関係を利用して除去を行う.また,配列に関する言語仕様を符号拡張命令の除去に利用し,さらに符号拡張命令をより実行頻度の少ない場所に移動させることも行っている.我々はこのアルゴリズムを現在開発中の64ビットアーキテクチャ向けのIBM Java Just-in-Time(JIT)compilerに実装して評価を行った.その結果,符号拡張命令の実行回数を平均で87?%削減することができた.我々の知る限り,本稿は符号拡張命令の除去を行う最初のアルゴリズムである.

Recently, 32 bit architectures are being shifted to 64 bit architectures. However, a program designed for a 32-bit architecture still uses many 32-bit data. For example, Java specifies ``int'' (which is the most frequently used type) as 32 bits. If such programs are executed on 64-bit architecture, many 32-bit data are necessary to be sign-extended to 64-bit data for integer type instructions. It causes performance degradation. At first, we implemented sign extension elimination based on data-flow analysis to improve performance. However, this approach could hardly eliminate sign extensions for array indices. Moreover, it could not selectively eliminate sign extensions from frequently executed points. In this paper, we present an effective new algorithm for eliminating and moving sign extensions. The same approach should work for any language and architecture requiring sign extensions. Our approach utilizes the dependencies on a variable to selectively eliminate sign extensions in order of frequently executed points. Additionally, it utilizes a language specification of the array type to eliminate more sign extensions, and moves sign extensions to rarely executed points. We implemented the algorithm in the IBM Java Just-in-Time (JIT) compiler for 64-bit architectures, which is under development. Our experimental results show that the execution count of sign extensions can be eliminated by 87% on average. To the best of our knowledge, this is the first algorithm for sign extension elimination.

収録刊行物

参考文献 (15)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ