課題研究 コード圧縮技術に関する調査研究 夜久健一

NAIST-IS-MR9951119
課題研究
コード 圧縮技術に関する調査研究
夜久 健一
2001 年 3 月 16 日
奈良先端科学技術大学院大学
情報科学研究科 情報システム学専攻
本報告書は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した課題研究の報告書である。
夜久 健一
審査委員：
福田 晃 教授
渡邉 勝正 教授
コード 圧縮技術に関する調査研究3
夜久 健一
内容梗概
組み込み機器では特に、物理的な空間や重量の制約、消費電力やコストなどの
観点で内部の資源に制限があることが普通である。一方で複雑な機能を持ったソ
フトウェアを実行する必要がある。通常こうしたソフトウェアは、機能が豊富に
なるに連れて肥大化し 、多量の資源を消費するものである。こうした事態を打開
するために、現状の資源の活用状況を見直しより有効に活用できるようにすると
言うことが考えられる。ここで重要になるのがコード 圧縮技術である。
本報告書ではこれまでに研究されてきたコード 圧縮技術に関して、特に実行
コードサイズを縮小するものに着目して調査を行った。基幹となる技術はパター
ンマッチングを応用してコード の冗長部を検索し 、ファクタリゼイションによっ
て圧縮するというものである。
今後のコンピューター利用は、ネットワーク及び組み込み分野に重点をシフト
していくと考えられるが、コード サイズを縮小するための技術はこれらの分野で
も広く使われることが見込まれ、そのために必要となる要素に主眼を置いて研究
が進められていることが分かった。
キーワード
コード 圧縮, 組み込みシステム, ネットワークコンピューティング , モバイルコン
ピューティング , パターンマッチング , ファクタライゼイション
3 奈良先端科学技術大学院大学 情報科学研究科 情報システム学専攻 課題研究,
MR9951119, 2001
年
3
月
16
日.
i
NAIST-IS-
3
Survey of Code Compression Techniques
Kenichi Yaku
Abstract
Most embedded systems have strong limitations with their inner resources,
because of physical spaces, weights, power consumptions and/or system costs. On
the other hand, these systems must run more complicated softwares. Clearly these
programs need much more system resources. Therefore, we have to analyze the
usage of limited resources and reallocate them more eectively. Code compression
techniques are very important at this point.
In this report, we survey many researchs about code compression, especially
about compacting executable codes. In this eld, the basic algorithm is to search
repeated code fragments with pattern matching, and to compact them with factorization techniques.
The main target of computer science will be shifted to network and embedded
systems. Code compression techniques are very useful in those elds and will be
developed to accept those demands.
Keywords:
Code Compression,Embedded System,Network Computing,Mobile Computing,Pattern
Matching,Factorization
3 Master's
Report, Department of Information Systems, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MR9951119,
ii
March 16, 2001.
目 次
1.
はじめに
1
2.
基幹技術
3
3.
既存の最適化手法
4
3.1
3.2
3.3
3.4
3.5
3.6
4.
不到達命令の削除
: : : : : : : : : : : : : : : : : : : : : : : : : : :
無駄な命令の除去
: : : : : : : : : : : : : : : : : : : : : : : : : : :
無効変数の削除
: : : : : : : : : : : : : : : : : : : : : : : : : : : :
共通表現の削除
: : : : : : : : : : : : : : : : : : : : : : : : : : : :
短絡
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
手続き呼び出し変換
手続き抽出
4.1 導入 : : : : :
4.2 圧縮機構 : : :
4.2.1 同定 :
4.2.2 評価 :
4.2.3 圧縮 :
4.3 その他の応用
5.
: : : : : : : : : : : : : : : : : : : : : : : : :
4
4
4
5
5
5
7
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : : : :
組み込み RISC
5.1 背景 : : : : : : : : : : : : : :
5.2 繰り返しの同定 : : : : : : : :
5.2.1 サフィックス木の構築
5.2.2 繰り返し表の作成 : : :
5.2.3 繰り返しの分割 : : : :
5.3 繰り返しの置換 : : : : : : : :
5.4 拡張 : : : : : : : : : : : : : :
5.4.1 分岐の抽象化 : : : : :
7
9
9
12
14
15
17
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : : : :
iii
17
18
18
19
20
21
23
23
5.4.2 レジスタ抽象化 : : : : : :
5.4.3 プロファイルに基づく選択
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
5.5 実験 : : : : : : : : : : : : : : : : : : : : : : : :
5.5.1 評価プログラム : : : : : : : : : : : : : :
5.5.2 結果 : : : : : : : : : : : : : : : : : : : :
5.5.3 コード 圧縮と既存の最適化との相互作用
5.5.4 プロファイル情報の利用 : : : : : : : : :
5.5.5 圧縮時間 : : : : : : : : : : : : : : : : : :
5.6 今後の拡張 : : : : : : : : : : : : : : : : : : : :
5.7 まとめと結論 : : : : : : : : : : : : : : : : : : :
6.
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
: : : : : : : : : :
23
30
30
31
32
33
34
36
36
38
組み込み Java システム
39
6.1 導入 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.2 Java バイトコード の圧縮 : : : : : : : : : : : : : : : : : : : : : : :
6.2.1 クラスファイルの縮小 : : : : : : : : : : : : : : : : : : : :
6.2.2 基本ブロック圧縮 : : : : : : : : : : : : : : : : : : : : : : :
6.2.3 メソッドとサブルーチン : : : : : : : : : : : : : : : : : : :
6.2.4 命令セット拡張 : : : : : : : : : : : : : : : : : : : : : : : :
6.3 簡単な例 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.4 ファクタリゼイション : : : : : : : : : : : : : : : : : : : : : : : :
6.4.1 パターン生成 : : : : : : : : : : : : : : : : : : : : : : : : :
6.4.2 パターン枝刈 : : : : : : : : : : : : : : : : : : : : : : : : :
6.4.3 パターン適用 : : : : : : : : : : : : : : : : : : : : : : : : :
6.5 拡張 JVM の実装 : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.5.1 マクロ表現 : : : : : : : : : : : : : : : : : : : : : : : : : :
6.5.2 JVM 主ループ修正 : : : : : : : : : : : : : : : : : : : : : :
6.6 性能評価 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.7 結論と今後の課題 : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.8 付録 A : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
6.9 付録 B : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
39
40
40
41
41
42
43
46
47
47
48
49
49
50
51
55
55
57
iv
7.
8.
比較検証
61
7.1
7.2
7.3
7.4
61
62
63
64
Cooper99 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Clausen98 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Sutter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Nystrom : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
まとめ
66
謝辞
67
参考文献
68
付録
70
A.
内容梗概
70
A.1 Fraser84 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.2 Cooper99 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.3 Clausen99 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.4 Runeson00 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.5 O'Sullivan94 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.6 Zastre : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.7 Debray99 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.8 Srivastava94 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.9 Lekatsas98 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.10 Proebsting95 : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.11 Vahid95 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.12 Liao95' : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.13 Lefurgy98 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.14 Zastre95 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.15 Sutter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
A.16 Nystrom : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
70
70
71
71
71
72
72
72
73
74
74
74
75
75
76
76
v
図 目 次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
XYXYZ の Sux-tree : : : : : : : : : : : : : : : : : : : : : : : :
9
第 2 段階 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
第 3 段階 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
bananas という文字列に対する Sux-tree : : : : : : : : : : : : : 19
制御条件の異なるプログラム断片 : : : : : : : : : : : : : : : : : : 20
手続き抽出の例 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21
クロスジャンプの例 : : : : : : : : : : : : : : : : : : : : : : : : : 22
類似不一致な断片 : : : : : : : : : : : : : : : : : : : : : : : : : : : 24
表現の変更 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25
存在範囲再配置の説明における各表現 : : : : : : : : : : : : : : : 27
再配置の例 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27
再割り当て : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28
隣接障害回避 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29
再帰処理 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29
評価プログラム : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31
プログラム特性 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32
結果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33
相互作用 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34
プロファイルに基づいた結果 : : : : : : : : : : : : : : : : : : : : 35
所要時間 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36
定数抽象化 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37
命令並べ替え : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37
バイトコード サイズ : : : : : : : : : : : : : : : : : : : : : : : : : 52
圧縮率グラフ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 53
マクロによる速度低下 : : : : : : : : : : : : : : : : : : : : : : : : 54
表 目 次
vi
1.
はじめに
コンピューターが社会で広く使われるようになって久しいが、近年では特に携
帯電話や多くの家電製品など 、様々な装置に組み込んで使われることが主流となっ
てきた。こうした組み込み機器では特に、物理的な空間や重量の制約、消費電力
やコストなどの観点で内部の資源に制限があることが普通である。中でも半導体
メモリは、このところ著しく低価格化、大容量化が進んではいるが、システム全
体のコストや消費電力に大きく関わるため厳しい制約があることが少なくない。
一方でユーザーの要求を満たすためには、組み込みシステムと言えども、携帯電
話の各種暗号化や情報端末の画像、音声処理など 、複雑な機能を持ったソフトウェ
アを実行する必要がある。通常こうしたソフトウェアは、機能が豊富になるに連
れて肥大化し 、多量の資源を消費するものである。
また最近では単体で動作するシステムと言うのはほとんど考えられず、ネット
ワークに接続されて協調動作をするシステムが増えている。ここでは個々の端末
の資源は組み込み機器に比べれば豊富に提供されているが、ネットワークの帯域
と言う資源にはやはり厳しい制約があることがよくある。ここでもユーザーの要
求に応える高度な機能を備えたソフトウェアと言うものが資源を多量に消費して、
深刻な資源不足を招いていることが容易に推察できる。
こうした事態を打開するためには 3 つの方法が考えられる。1 つは足りない資
源を増やすと言うアプローチである。勿論そのためにより小さく、低消費電力で
低コストな大容量メモリの開発などが続けられている。しかし資源と言うのはあ
ればあるだけ使われてしまうと言う宿命があるので、これだけでは心もとない。
また 1 つには資源の限界を超えないようにシステムが提供する機能を制限すると
言うアプローチもある。しかしこれは否定的な解決法でユーザーの要求に応えら
れていない。
第 3 のアプローチとして、現状の資源の活用状況を見直し 、より有効に活用で
きるようにすると言うことが考えられる。つまりコード 圧縮技術を利用して、高
度な機能を備えていながら小さなソフトウェアというものを用意するのである。
こうして同じ機能ならば必要な資源の量を減らし 、資源の量が同じであればより
高度な機能を提供できるようにするというものである。
1
実行プログラムから無駄な部分を省くというのは新しい考え方ではない。古典
的なコンパイラの最適化手法においてもしばしば見られるものであるが、従来で
はこうした最適化は未使用のコードをファイルから削除することで、コード サイ
ズを縮小するというよりも実行速度を改善することを目的にしてきた。しかしこ
れらの技術も当然ソフトウェアの縮小に応用できる。
またコード 圧縮技術そのものにも、コードを圧縮して格納し 、実行時に必要な
部分を解凍しながら実行する方法や専用のハードウェアの支援を受ける方法、実
行可能な形態のままで圧縮する方法などが研究されている。そこでこれらの技術
を体系化して調査し 、比較検証することで今後の研究への参考資料を提供するこ
とが本報告書の目的である。
以下に報告書の構成を述べる。2章では、コード 圧縮の基本となる考え方につ
いて述べる。3章では、古典的な最適化手法とコード 圧縮技術の関係について考
察する。4章では、Fraser らの研究による Procedural Abstraction[1] について説
明し 、5章で、Cooper らによる特に組み込みシステムにおいて重要な拡張 [2] に
ついて述べる。6章では、Clausen らによるネットワークコンピューティングを考
慮した Java 環境でのコード サイズ縮小 [6] について論じ 、7章で、様々な方式の
長所と欠点を比較検討する。最後に 8章で今後の課題について考察する。また、
付録 Aに参考文献の一部の内容梗概を添付する。
2
2.
基幹技術
データ圧縮の基本となるのは、冗長度の削減である。様々なパターンマッチン
グ技術を用いて冗長性を有した重複パターンを検索する。そして代表パターンを
残して他の部分にはそのパターンを参照する印をパターンよりも小さな表現方法
で置き換える。こうしてパターンサイズと印のサイズの差とパターンの出現回数
で削減できる情報量が決まるのである。
プログラムコードにおいてもこの基本は変わらない。そこでまずパターン探索
を行うのであるが、プログラムの場合特に、どんなパターンに対してもパターン
自体よりも小さなパターン参照を示す表現が存在するとは限らない。また表現方
法だけは存在しても、一般に実行できるプログラムの状態を保てなくなる場合も
ある。
こうした点を踏まえて 、コード 圧縮においては制御フローグラフのパターン
マッチングと各命令を 1 つの記号と見なした記号列パターンマッチングの技術が
よく使われる。このような形で得られるパターンは、手続き呼び出しやマクロ表
現などを利用して、実行可能なプログラムでありながらパターン自体よりも小さ
な表現に変換しやすいからである。
3
3.
既存の最適化手法
古典的なコンパイラの最適化手法としては、主に実行速度の改善に主眼を置か
れたものが多いが、結果としてコード サイズの縮小に繋がる最適化もある。本章
ではこのような最適化について簡単に説明する。
3.1
不到達命令の削除
構造化されたプログラムである命令が実行されなくなる場合というのは大きく
分けて二つある。条件分岐の判定結果が事前に分かっている場合と、一回も実行
されないループがある場合である。構造化されていないプログラムではこのよう
な実行されない命令を探すことは難しくなるが、制御フローグラフを追跡するこ
とで見つけることが出来る。
不到達命令も無駄な命令も定数伝播によって生じることがある。またこの二つ
の命令などの冗長部を削除することによってさらに定数伝播が可能になることも
あるので、コンパイラによっては定数伝播を最適化の過程で複数回行う。
不到達命令の除去と分けて考えられることもあるが、除去された結果実体のな
くなった分岐命令も無駄な計算と考えられしばしば削除される。
3.2
無駄な命令の除去
無駄な命令というのは他の最適化を施すことによって生じることがある。コン
パイラはある命令によって計算された値が不要なものであると判明したら、その
コードを削除する。この変換は代入直後に不要となる全ての局所変数に対して適
用できるが、不要であるかど うかの判断は有名なデータフロー問題として知られ
ている。
3.3
無効変数の削除
一連の変換、特にループ最適化の後に、全く使われない変数というのが生じる
ことがある。この場合こうした無駄な変数そのものを削除することもよくある最
4
適化である。
3.4
共通表現の削除
一連の計算が同じ部分式を持つことがよくある。このとき式を毎回コーディン
グすると同じ命令を繰り返すのと、同じアドレス計算を繰り返すのとで無駄が生
じる。そこでこの部分式を一回計算したらその結果を保存しておいて再利用する
という最適化が考えられる。しかし 、このときコンパイラはその結果を保存して
おくことによって生じる trade-o を十分考慮する必要がある。
3.5
短絡
これは論理式に対する最適化である。複雑な論理式の評価が先頭の式で決めら
れる場合があるため、全てを評価せず、先頭の式が一致しなければ偽として処理
を継続することで真偽判定のオーバーヘッドを減らすことを目的としている。し
かし 、評価式の中に変数書き換えなどの副作用がある場合は、変数参照を監視し
ておいてこの変換によって結果が変わるかど うかを考慮しなければならない。
3.6
手続き呼び出し変換
この節では、今回の圧縮のアプローチとは方向性が異なるが、以下の 4 つの手
法を利用して手続き呼び出しの負荷を減らす変換について述べる。
呼び出し自体を削除先に述べた無駄な命令の除去とも重なるが、必要のな
い呼び出し手続きを削除する。
呼び出された手続き本体の実行部分を削除同様に手続きの実体内に不要な
命令が含まれる場合などにこれらを削除する。
手続き間の移動に伴なう負荷を削減手続き呼び出しの際には、様々なパラ
メータを受け渡すような負荷が生じるが、こうした負荷を最小限に済ませ
られるように変換する。
5
呼び出される手続きの振る舞いが分かっている場合や、他の物に変えられ
る場合呼び出しの数ステップを避ける実体が小さな手続きの場合、呼び出
すよりもその場に実体を展開してしまう方が負荷は少なくなる。
このうち前半 2 つはコード サイズの縮小にも貢献するが、3 つめの手法はレジ
スターなどが豊富にある環境でそれを有効に使うことを考慮しているので、組み
込み機器などの資源に制約のある環境では有効ではない。また最後の手法は実行
速度のみに着目していて、今回調査した圧縮の為の基本となる考え方とは正反対
のアプローチである。
6
4.
手続き抽出
4.1
導入
ほとんどの最適化は実行時間最適化に着目している。領域を最適化するものも
あるが、多くはプログラムを長くすることで実行速度を上げるものである。例え
ば インダクション変数の削除、ループ展開など 。
領域を節約する最適化は、例え時間を消費するものであってもほとんど研究さ
れていない。こうした中で、手続き抽出とクロスジャンプは最も重要なものであ
る。手続き抽出と言うのは繰り返されるコード 断片を手続き化し 、機種依存を避
けるために普通中間コードやソースコードに対して適用される。しかしそのため
にコード 生成時に発生する断片に関しては見落とされてきた。クロスジャンプは
合流する二つのコード 列の共有尾部を共用する手法で、例えば次のような置換が
なされる。
X
Jump L1
・
・
・
X
L1：Y
を
Jump L2
・
・
・
L2：X
L1：Y
に
クロスジャンプは通常実行コード 生成後に行われる。これは並列性が事前には
分かりにくいからである。クロスジャンプと手続き抽出は実装系においてコード
が重なることはめったにない。
7
本章では一般的なデータ圧縮アルゴ リズムをアセンブラコードに適用する手法
について述べる。これは手続き抽出とクロスジャンプを含めたもので、極端な例
を挙げれば 、この圧縮法によって 27 の断片 X を連続で実行するプログラムは次
のように圧縮される。
Main：
Call subr1
Call subr1
Call subr1
Exit
Subr1：
Call subr2
Call subr2
Call subr2
Subr2：
X
X
X
Return
これはメインルーチンで subr1 を三回呼び出し 、subr1 では実行されるたびに
subr2 を三回実行し 、subr2 は X を毎回三度実行すると言うものである。4.2 節で
はコード 圧縮の実装について述べる。
実装は単なる空間最適化以上の機能を持つ。全体をサブルーチン化するように
指示すると圧縮機構は、例え単一の小さな断片でもアセンブラコードをスレッド
化しコンパイラで直接実行できるコードも逐次的に実行できるコードも生成でき
るようにする。圧縮機構は同時にアセンブラコードを解析してその構文も同定す
る。こうしてコンパイラとアーキテクチャーのデザインにおける共通問題の解決
が容易になる。コンパイラ設計者は常にどこに最適化の焦点を置くかを決めなけ
ればならないが、構文の自動解析ができればこの探索も容易になる。アーキテク
チャーの設計者も求められるアプリケーションに適した命令セットを見つけなけ
8
XY Z
XYZ
1
5
Z
3
Y
XYZ
2
Z
4
図 1 XYXYZ の Sux-tree
ればならないが、文脈の自動的な解析によって明らかな候補が示され、デザイン
を伝統的な行き当たりばったりの方式ではなくて科学的な根拠に基づいて進める
ことができる。4.3 節でこうした応用例について論ずる。
4.2
圧縮機構
コード 圧縮機構は 3 段階の論理に基づいて動作する。繰り返されるコード 断片
の同定、抽出する適正度の評価、そして実際のプログラム圧縮である。以下の各
節で各段階を説明する。
4.2.1
同定
他の一般データに対する圧縮アルゴ リズムと同様、コード 圧縮機構も入力プロ
グラムに対するサフィックス木あるいはパトリシア木を構築するところから始ま
る。記号列 S に対するサフィックス木は S の部分文記号列で名づけられた枝と記号
列内での位置で名づけられた葉を持つ。例えば文字列 XYXYZ に対するサフィッ
クス木は図 1のようになる。
根から葉にいたるパスの名前は記号列の接尾語と一対一に対応する。例えば
XYXYZ に対して 2 番目から始まる接尾語は YXYZ で、根から２とついた葉ま
でのパスの枝の名前はまさしく YXYZ となっている。枝につけられた部分記号
列は普通その先頭と末尾の文字を格納して表現される。こうしてサフィックス木
は入力長に対して線形な空間内に格納される。
サフィックス木は逐次的に構築される。各段階で 1 つの葉が木に加わる。例え
ば先の木を構築する場合 3 段階では１と２の葉を持つ木を３の葉を加えて図 2か
9
XYXYZ
YXYZ
1
2
図 2 第 2 段階
XY
XYZ
1
YXYZ
2
Z
3
図 3 第 3 段階
ら図 3次のようにする。
SUF(K) を K 番目からの接尾語とし 、HEAD(K) を SUF(K) に対する最長接頭
辞とする。先の例に対する実装では、HEAD(K) の長さに対して K ステップの時
間を所要するように見えるので、完全な木を構築するには膨大な時間がかかる。
しかし 、HEAD(K) は HEAD(K-1) の末尾から延長されるので、アルゴ リズムを
もう一度見直すと各文字は一回以上再読み込みをする必要がないことがわかる。
こうして木全体は線形時間内に構築できる。こうしたアルゴリズムに対する厳密
な考察は本章の範疇を超えるが、参考文献の [7] などで見ることができる。
サフィックス木によって共通部分記号列が同定できる。内部の節点が M の葉を
持つ部分木を指していたら根からその節点にいたるパス上の記号列が M 回出現
していることになる。例えば先のサフィックス木なら根から左の葉に繋がる枝は、
１と３という二つの葉を持つ部分木を指しているので文字列 XY は入力中に 2 回
出てくることが分かる。
このアルゴ リズムは普通文字列に適用されるが、各記号が文字でなくプログラ
ムの原始要素であるような記号列にも同じように適用できる。コード 圧縮機構は
命令をハッシュ表に読み込んで、同じ命令が同じアドレスになるように配置する。
こうして圧縮機構は文字列ではなくてハッシュアドレスを圧縮する。
10
アセンブラコードを読むと、一部の要素が欠落することがある。データの型指
定などは直接出力されてしまう。これでは有用なコード 断片を生成することがで
きないし 、コードに直接含まれている場合は本来圧縮できたはずの断片の同定を
複雑にしてしまうかも知れない。ラベル定義は消えてしまうことはないが、繰り
返される断片を同定する際に隠されてしまう。しかし隠さなければラベルのつい
た本来同定されるべき断片を、ラベルが一致しないから違うものと認識されてし
まう。4.2.3 でこのラベル隠蔽がコード の同一性を損なわないことを示す。
サフィックス木を構築するアルゴ リズムは頻繁に命令の比較を行わなければな
らない。ほとんどの命令に対してはこれは単にハッシュアドレスを比較すればす
む。というのは二つの命令はそのアセンブラコードの字面が同じならば同じと考
えられるからである。しかしこの条件は分岐に関して緩和でき、圧縮の可能性を
増やすことができる。例えば同じラベルに対する分岐は同じとみなせる。多くの
コンパイラでは複合ラベルを特定の場所に生成する。例えば条件文は普通ラベル
で終わるし 、多くのループもラベルで始まる。だからループにつながる条件分岐
は同じ場所に二回ラベル付けをする。コード 圧縮機構は見かけ上の不一致を、命
令を読む際に同一のラベルに関して知らせることでなくすことができる。極端に
言えばアセンブラの指令を同一のシンボルに変換することもできる。
命令比較機構は相対分岐にも対応している。数命令を飛ばす分岐があるために
同定できない命令断片を考えてみると、それらが異なるラベルを参照しているた
めに記号上は異なるが、もし両者が同じ距離をスキップしているのなら二つの断
片は 1 つにできるかもしれない。このように二つの分岐に対してそれらが絶対的
に (同じラベルに分岐する) 、もしくは相対的に (同じ距離だけ分岐する) 同一の
ものであれば同一の記号であるとみなすことができる。距離は単に命令数を数え
ることによってマシンに独立して計算できる。命令の大きさを考慮する必要はな
い。というのもコード 圧縮機構は相対分岐をそのターゲットを再配置することな
く移動させることはできないからである。だから相対分岐を含む二つの断片は、
まずその分岐が間を飛ばす命令列が同じかど うかを判定してからでなければ 1 つ
にはできないのである。
再利用を容易にするために、コード 圧縮機構の機種依存性はパターンに分割さ
11
れる。例えば UNIX の PDP-11 アセンブラに対するパターンは
%%ujump
jbr %1
jmp %1
%%label
%1:
無条件分岐は jbr および jmp から始まり、%1 という引数をとってラベルはコロ
ンに繋がる文字列であるということを宣言している。UNIX の PDP-11 アセンブ
ラに対する完全なパターンファイル（条件分岐や手続き呼び出しを含む）はこう
したパターンの集まりである。
4.2.2
評価
繰り返されるコード 断片が同定されたら、それを手続き化する正当性を評価し
なければならない。というのも例えば断片によっては短すぎて手続き抽出に向か
ない場合もあるからである。こうしてサフィックス木が生成されるとコード 圧縮
機構はそれぞれの断片に対応する木の節点を順に調べていく。各断片の実体のリ
ストは節約される命令数、つまり共通のコピーに置き換えられる命令数を返す機
能に引き渡される。この値が負であればその断片は置き換えない方が良いことが
分かる。
「閉じた」すなわち最後のコードが
評価の為には 2 種類のコード 断片がある。
実行されて断片から抜けるものと、
「開けた」すなわち外部への非相対分岐を含
む断片である。
「閉じた」断片はサブルーチンとして実装され、呼び出して続き、
復帰処理がコードを増加させる。したがって評価機能はこうしたコストを表現す
るパラメーターを利用するので、通常複数命令を含むサブルーチンに対してのみ
正の評価を下す。
「開けた」断片は直接ジャンプなどで実行され 、このアプロー
チはオリジナルと変わらないので常に正の評価が下されることになる。
候補となる断片は綿密に検査される。例えば上述のように、断片が相対分岐を
含む場合その分岐先も含まなければならない。というのも分岐を再配置しながら
分岐先を放置しておけばプログラムの結果が変わってしまうからである。
12
「閉じた」断片もサブルーチンとして実装されるから、直接その領域に出入り
するジャンプは禁止される。対照的に「開けた」断片は直接その領域へ入ること
になる。従ってその末尾から次の命令にそのまま続けると結果が変わってしまう
ことになる。繰り返すが違法な断片は実行不能なコードをのぞく為に分割される。
またネストせずに重なっている断片も圧縮できない。例えば ABABCBC に対
するサフィックス木は AB と BC が二つずつあることを示すが、二つ目の AB と
一つ目の BC は重なっているので、両者のどちらかだけが置換できる。
最後に「閉じた」断片への呼び出しがスタックに影響を与える場合、こうした
断片はスタックに積んだものを正確に取り除かなければならない。例えばスタッ
クからの読み込みで始まるような断片はサブルーチン化されると予期せぬアドレ
スをスタックから取ることになる。これを解決するために先のようなパターンで
は行末にスタックの調整パラメータを拡張する。例えば
Pattern
Stack Adjustment
mov %1,-(sp) 2
add %1,sp -%1
のように mov ｘ,-(SP) でスタックに 2 バイト追加し 、add n SP で n バイト
減算する。
（ PDP-11 のスタックは下へ伸びるので加算命令はスタックから減算
する。）評価機構はスタック以外問題のない候補となるサブルーチンを走査する。
もしサブルーチン全体がスタックに問題がある場合ルーチン外のスタックにアク
セスする命令を印付けて、サブルーチンはこの破棄される命令で分割される。検
査は以下のようなアルゴリズムに集約される。サフィックス木の節点が計算され、
それが示す繰り返し断片が慎重に評価される。ここでは上の検査は行われない。
断片は見積もられた節約量に基づく優先度つき待ち行列に並べられる。完了する
と最も有望な断片が行列から取り出され上述の検査が行われる。全てのチェック
を通るとプログラムは次節で述べられるように書き直される。そうでなければ問
題になる命令が分割されるか破棄され、残る部分は再び行列に投入される。そし
て次に有望な断片が取り出されて検査される。こうして行列から候補がなくなる
までこの過程は繰り返される。この手法は VAX11/780 上で秒間 80 ∼ 100 命令
を圧縮処理できた
13
4.2.3
圧縮
「閉じた」断片はサブルーチン化され、それぞれはサブルーチンへの出入りの
ための処理が加えられた後、末尾の欄外へ移動される。各断片はそれぞれのルー
チンへの呼び出し処理に置き換えられる。もし開始手続きが空欄であれば 4.1 節
の例のように各ルーチンは次のルーチンへと継続処理をしてしまう。
「開けた」断片の場合は単なる分岐と置き換えられる。
「閉じた」断片と同じ
ように本体はプログラムの末尾に移動し 、それぞれの断片は本体への分岐に置き
換えられる。しかし 、最後の断片を残すようにすれば 、そこへは分岐せず継続処
理できるので少し効率が良くなる。こうすればクロスジャンプを効率的に実装で
きる。
先に解説したように、ラベルの違いは繰り返しの断片を同定する段階で隠蔽さ
れる。ここで誤った断片が導入される心配はない。
「閉じた」断片は先頭からし
か入れないので、ラベルは全て構成を検査済みの内部の相対分岐用である。一方
で「開けた」断片にはどこからでも入れるから圧縮機構は一般性を失わずにその
ラベル定義を入れ替えられる。例えば
A
L1：B
C
Jump L3
と
A
B
L2：C
Jump L3
は
A
14
L1:B
L2:C
Jump L3
としても一般性を失わない。
圧縮機構を 157 の UNIX ユーティリティーを含む一連のプログラムに対して実
行した結果、プログラム毎に異なる結果となったものの圧縮率は 0-39%で平均7% 、
CPU 時間で1-5%の増加をしたものの、読み込み時間の短縮で実時間では11%の高
速化をもたらした。
4.3
その他の応用
通常の評価機構によると複数の命令を含んで複数回繰り返される「閉じた」断
片による節約だけが報告された。一方でこの節約できる可能性はまだ十分活用
はされていない。その閾値は可変であり、1 命令で 1 回だけのサブルーチンの生
成にも対応できるかもしれない。結果的にプログラムは分岐とサブルーチン呼び
出しのリストと、それに続くサブルーチン本体のリストになる。呼び出しのサブ
ルーチンのアドレスはスレッド 化されたコードを生成し 、サブルーチン本体はイ
ンタープリターを構成する。こうして圧縮機構は同一のコンパイラで実行コード
もインタープリター用のコード も生成させることができる。
圧縮機構はまたアセンブラの解析にも有用である。オプションとして各繰り返
しの命令数と長さをオリジナルと圧縮後のプログラムにおいて記録しておくこと
ができる。こうした情報は直接利用したり、共通の構文を見つけ出したりするの
に有効である。例えば
ピープホール最適化機構から流用したプログラムで各断片のｎ番目の数値や変
数名を%n という文字列に置換する場合、次のような断片の記録
mov _i,r1
mul #10,r1
add _j,r1
を
15
mov %1,r%2
mul #%3,r%2
add %4,r%2
に変える。これは上の断片が一例となるような一般的な構文を示している。大
量のテストプログラムに対する構文の出現頻度の報告があれば 、コンパイラの
製作者は最適化の努力をどこに集中するべきかが分かるし 、機械設計者にとって
も適切な基本要素を見つける助けとなるだろう。こうして古いシステムのソース
コード 操作頻度や複数の手作業で書かれた並列アセンブラコードの出現頻度を決
定する基本要素を同定する手助けとなる。こうした古い解析は大抵かなり手軽に
実行できるが、このシステムは全ての構文を自動的により長い構文としてリスト
アップできる。
16
5.
5.1
組み込み RISC
背景
ますます、実行コードの大きさはコンピューターシステムの性能とコストに大
きな要因となってきている。携帯電話のような組み込み機器から、WWW による
アプレットまで、コンパイル時にコード サイズを拡大する決定が大きな衝撃とし
て感じられる。携帯電話においてはコードサイズがコストと電力消費に直結する
し 、ウェブ上のアプリケーションではユーザーは転送時間と実行時間の両方を待
たなければならない。他にも多くの例が、コード サイズがアプリケーションの性
能と価格に直接影響するものとして挙げられる。
実行コードのサイズは多くの要因によって決まる。動作環境の命令セットも強
い影響がある。例えばスタックマシンは小さなコードで実行できることで知られ
ているし 、3 アドレスの RISC アーキテクチャーは各オペランドが厳密に名づけ
られることなどを原因としてより大きなコードを生成する。特定の変換が最適化
時に適用されるためにコンパイラに選ばれる特定のコード 列も影響する。
本章はコンパイルの最終段階で圧縮するコードサイズ縮小のための一手法につ
いて調査している。本手法の概念は単純である。Fraser らによる VAX アセンブ
ラのための研究 [1] に基づいている。パターンマッチング手法によって同じコー
ド 列（以下繰り返し ）を同定するものである。コンパイラはそれから手続き抽出
かクロスジャンプによって繰り返しの実行を単一のコードに交換する。この基本
アルゴ リズムにレジスタ名を分離することで同一の条件を緩める拡張を行った。
グラフ塗り分けによるレジスタの割り当て法と併用してコード 圧縮をする場合の
鍵となる拡張である。
本章ではいくつかの異なる主眼がある。まず、RISC アーキテクチャーにおけ
るコード 圧縮の総括的な実験評価を行った。実験したテストプログラムでは平均
で 5% 、最大15%の圧縮効果が見られた。次に古典的なスカラー最適化のコード ス
ペースに対する効果を評価し 、これらの最適化とコード 圧縮との相互作用を調査
した。結果はこの二つの手法は領域に対する効果で競合的というよりはむしろ相
補的であった。3 つめに、基本となる圧縮法にレジスタ割り当てが異なる場合を
17
処理する手法を提案し評価した。実験によればこの処理によって圧縮手法の性能
はかなり向上した。最後にコード サイズと実行時間との trade-o をコントロール
する機構を提供するプロファイルに基づく手法を紹介する。
本章は以下のように構成されている。2 節、3 節は繰り返しを本手法がどのよ
うに同定し 、1 つの共有の実体への参照と交換していくかを説明する。4 節では
レジスタ名の微妙な違いを本手法が隠蔽できるようにしている拡張に関して説明
する。5 節は一連のベンチマークに対して本手法を適用した一連の実験結果を示
す。6 節ではコード 圧縮やコード 空間の最適化に関する他の関連研究と本研究の
比較を行う。7 節では今後のコード 圧縮に対する研究のアイデアを紹介する。最
後に 8 節で本研究の成果をまとめ、結論を述べる。
5.2
繰り返しの同定
本手法の第一の要件はプログラム中の全ての繰り返しを見つけて、圧縮すべき
繰り返しを選択する事である。繰り返しを同定するために Fraser らと同じように
サフィックス木を構築する。
5.2.1
サフィックス木の構築
サフィックス木は文字列の繰り返しに関する情報を内包したデータ構造である。
サフィックス木は様々なパターンマッチングの応用に利用される。文字列 S が与
えられたとき、S をあらわすサフィックス木の枝は S に含まれる部分文字列でラ
ベル付けされる。木の根から葉にいたるパス P にそった枝のラベルは S の特定の
接尾辞を表す。図 4は bananas という文字列に対するサフィックス木の例である。
根以外の各中間節点は入力の繰り返される部分文字列と一致し 、圧縮できる可能
性を示す。長さ N の文字列に対するサフィックス木は O（ N ）時間で構築できる
ので、コード 圧縮の道具として期待できる。
サフィックス木を構築するためには、各命令をハッシュして、全体を表にまと
める必要がある。オペコード、レジスタ名、定数の組が同一の命令は文脈的に同
じ命令を調べた後、表の同じ場所に格納される。例えば iADD r9,r10 → r10 と
iADD r10,r9 → r10 は整数の加算が可換であることから同じ命令とみなされる。
18
S
S
NA
NAS
BANANAS
A
S
NA
S
NAS
図 4 bananas という文字列に対する Sux-tree
こうして表の各要素は同じクラスの命令に対応することになる。
次に線形の文字列に似たテキストと呼ばれるプログラムの表現を生成する。そ
の各文字はプログラムにおける命令に対応する。テキストの K 番目はプログラム
の K 番目の命令からハッシュされ、命令表から要素の目次を得るために計算され
る。ひとたびプログラムを表現するテキストが構成されれば 、Ukkonen のアルゴ
リズムによって実際のサフィックス木が生成される。
5.2.2
繰り返し表の作成
サフィックス木から得られる情報は繰り返し表と呼ばれるデータ構造で格納さ
れる。表の各要素は断片の集合、つまり特定のテキストにおける部分文字列とな
る。図 5は 2 つの同じ断片からなる繰り返しの例である。内部では断片はテキス
トにおける位置と長さを示す整数の組として格納されているように表現される。
繰り返しが圧縮過程の素材となる。K 断片の繰り返しが与えられたら、K-1 の断
片を最後の実体への参照に置き換えることが目標である。
一連の断片が繰り返しの候補として集められた後、コンパイラは変換を妨げる
ような条件がないことを確認するために解析しなければならない。こうした条件
を制御危機といい、手続き抽出やクロスジャンプを妨害するような断片内部への
ジャンプや内部からのジャンプに対応する。
図 5ではどちらの断片も制御の流れが変わる命令を含んでいない。しかし断片
19
…Fragment F2…
…Fragment F1…
MUL r3,r4r5
L1:MUL r3,r4r5
ADD r2,r5r9
ADD r2,r5r9
LOAD [r9] r1
LOAD [r9] r1
ADDI r1,10r8
ADDI r1,10r8
STORE r8 [r9]
STORE r8 [r9]
LOADI 4 r7
LOADI 4 r7
ADD r7,r9r9 L9:ADD r7,r9r9
LOAD [r9] r1
LOAD [r9] r1
ADDI r1,10r8
ADDI r1,10r8
…
…
図 5 制御条件の異なるプログラム断片
F2 は 2 ブロック以上に渡るので、F2 の内部の命令が外部からの分岐の対象となっ
ているかもしれない。この種の危険はこの断片の圧縮を不安定にするかもしれな
い。
（ 5.3 節で安全性に対する特性について述べる）
5.2.3
繰り返しの分割
繰り返しマネージャーが繰り返し内部の変換を妨げる危険を確認すると、大抵
繰り返しを分割することでその状況に対処する。N 回の繰り返しが与えられた場
合、特定の位置で各断片を分割すると、二つの新たな小さい N 回の繰り返しが生
成される。例えば図 5で圧縮機構は 5 番目の位置で繰り返しを分割し 、2 回繰り
返す新たな断片を 2 つ生成することで、二つ目の断片の制御危機を回避できる。
繰り返しマネージャーは与えられた繰り返しをいつどこで分割するか決めるた
めに詳細なコストモデルを使用する。それは断片の長さや、危険の位置や種類、
危機を示す断片の数などを考慮したものである。多くの場合マネージャーは制御
危機を違反しているジャンプポイントで分割する。結果として断片があまりにも
小さくなる場合は危険を含んだ断片を繰り返しから除く。
20
…Region 1…
NEG r10 r1
ADD r2,r3r4
LOAD [r4] r7
SUB r7,r8r9
MUL r9,r7[r4]
…
…Region 2…
SUB r9,r8r1
ADD r2,r3r4
LOAD [r4] r7
SUB r7,r8r9
MUL r9,r7[r4]
…
Original Code
…Region 1…
…Region 2…
NEG r10 r1 SUB r9,r8r1
CALL ts1
CALL ts1
…
…
…Abstract Procedure…
ts1:ADD r2,r3r4
LOAD [r4] r7
SUB r7,r8r9
MUL r9,r7[r4]
RTN
Abstracted
図 6 手続き抽出の例
5.3
繰り返しの置換
コンパイラは圧縮のための繰り返しの実体を収集すると、コード を変換する。
本手法ではこのために二つの異なる変換を利用する。手続き抽出とクロスジャン
プである。
図 6は手続き抽出の例である。この変換では与えられたコード 領域は手続き化
され、他の同一の領域は新しい手続きへの呼び出しに置き換えられる。手続き抽
出は候補領域への出入り口が 1 つずつである必要がある。内部でのジャンプは手
続き本体内で完結しなければならない。
図 7はクロスジャンプ（尾部結合としても知られている。）の例で、同じ対象へ
のジャンプで終わる同一の領域を結合するものである。この変換では、領域は直
接他の同一領域へのジャンプに置き換えられる。全ての領域での外部分岐はクロ
スジャンプを適用するためには同一でなければならない。
21
…Region 1…
ADD r2,r3r4
LOAD [r3] r7
SUB r7,r8r9
STORE r9[r4]
JMP L3
…
…Region 2…
MOV r9 r3
LOAD [r3] r7
SUB r7,r8r9
STORE r9[r4]
JMP L3
…
Original Code
…Region 1… …Region 2…
ADD r2r3r4
MOV r9 r3
JMP L5
L5:LOAD [r3]r7
…
SUB r7,r8r9
STORE r9[r4]
JMP L3
…
Cross-Jumpped
図 7 クロスジャンプの例
この変換はどちらもコード 領域の観点からも実行速度の観点からもある程度の
コストがかかる。例えば 、抽出された手続きを作る場合コンパイラは手続きの最
後に復帰のための命令を加えなければならないし 、手続きが参照される全ての場
所に呼び出し命令を挿入しなければならない。クロスジャンプの場合は、ジャン
プ命令が加えられる。結果としてこれらの変換は得られるものが命令のオーバー
ヘッド よりも大きい場合にのみ利用されるべきである。
繰り返しの選別
どの繰り返しを圧縮するかを選択する戦略は単純である。コンパイラは各繰り
返しの節約量の予測を計算して、繰り返し表を節約量で並べなおし 、並んだ順に
変換を適用するのである。
繰り返しが重なる場合もあることから、コンパイラはコード 断片を 2 回以上圧
縮しないように気をつけなければならない。そのために、すでに変換されたプロ
グラムは抜き出して、すでに圧縮された断片は通過するようになっている。
他の選択手法もいくつか実験している。5.4.3 節ではプロファイル情報を使って
22
プログラムの特に頻繁に実行される部分には変換を適用しないようにする拡張戦
略について説明している。
5.4
拡張
文字による同定を利用しているために、サフィックス木による手法の適用性が
制限されている。命令ごとの厳密な一致の必要性が、圧縮機構が探せる繰り返し
を必要以上に制限しているのである。二つの断片が似ていて、ラベルやレジスタ
名だけが違うと言うことが良くある。システムが探せる繰り返しの集合を増やす
ために、レジスタ名とジャンプ対象の抽象化手法を実験してみた。サフィックス
木の機構上データはテキストベースであることから、これらの変換はある命令を
ワイルド カードで置き換えることに対応する。もしこうして抽象化された断片を
元のプログラムの意味を損なわずに扱えるように手法を改良できたらコード 圧縮
全体を改善できるだろう。
5.4.1
分岐の抽象化
同一性の表現を緩める最初の段階は、Fraser らの研究のように分岐を可能な限
りプログラムカウンタ相対の形に書き換えることである。ハードコードへの分岐
は、それがなければ同一のコード 列を異なるラベルに分岐させるので繰り返しを
終わらせてしまう。こうした分岐をプログラムカウンタ相対に書き直すことで、
サフィックス木を構築するアルゴ リズムが複数のブロックにまたがる繰り返しを
発見できるようになる。実際分岐を抽象化する前はブロック間にまたがる繰り返
しはほとんど発見できなかったが、書き直してからは多くのブロックにまたがる
繰り返しを見つけるようになった。
5.4.2
レジスタ抽象化
レジスタ利用に関するわずかな違い以外は二つのコード 断片が同じと言うこと
がよくある。図 8のような例を考えてみる。この二つの断片は、オペコードは同
一であるが、初めの断片が r7 を使うところで二つ目の断片が r6 を使い、その逆
になるところで異なるレジスタを利用している。
23
…Fragment 1…
ADD r2,r3r4
LOAD [r4] r7
SUB r7,r3r9
STORE r9 [r4]
ADDI r416r5
LOAD [r5] r6
SUB r6,r4r9
STORE r9 [r5]
…
…Fragment 2…
ADD r2,r3r4
LOAD [r4] r6
SUB r6,r3r9
STORE r9 [r4]
ADDI r416r5
LOAD [r5] r7
SUB r7,r4r9
STORE r9 [r5]
…
図 8 類似不一致な断片
この二つの断片の圧縮を可能にする新しいコード 圧縮戦略を説明する。次のパ
ラグラフでこの戦略の最初の要素であるサフィックス木構築の前に行われる特定
のレジスタ名の抽象化をする書き直し段階について説明する。第二の要素はその
次のパラグラフで述べられる名前の変更段階で、ある断片で使われているレジス
タを他の断片と字面上同一にするために変更する部分を探すものである。本研究
では入力プログラムに対するレジスタ割り当てはすでに完了していると仮定して
いる。
相対レジスタパターンマッチング
相対レジスタ命令比較によって、サフィック
ス木を構築する前処理段階として以下の処理を行う。R1,r2, …,rn のレジスタ参
照を含む命令 I が与えられたとき、各レジスタ参照を、I を含む基本ブロックで
の前回の利用や定義の表現で書き直す。命令 I がレジスタ rk を読むとき、現在の
基本ブロックでの rk の定義か rk に対する前回の参照を探す。もし命令 Q におい
て rk への参照があった場合、I の rk に対する参照を<O,T,R>の三つ組みで書き直
す。ここで、O は Q と I の相対位置で、T は Q における参照の種類、R は Q で
使われているインデックスである。事前の参照が存在しない場合は、その参照を
ワイルド カードの印として *に置き換える。ブロック内の全てのレジスタ定義は *
に置き換えられる。図 9は図 8から抜き出した断片の 1 つで、レジスタ参照は相
対位置表現に置き換えられた後の同一断片である。
24
…Original…
L1:ADD r2,r3r4
LOAD [r4] r7
SUB r7,r3r9
STORE r9 [r4]
ADDI r416r5
LOAD [r5] r6
SUB r6,r4r9
STORE r9 [r5]
…
…References…
L1:ADD
* , *
*
LOAD <-1,d,0>
*
SUB <-1,d,0>,<-2,u,1>*
STORE <-1,d,0>
*
ADDI <-1,d,0>16
*
LOAD <-1,d,0>
*
SUB <-1,d,0>,<-3.d,1>*
STORE <-1,d,0>
*
…
図 9 表現の変更
25
命令を相対表現で書き換えることで、サフィックス木において字面が完全に一
致してなくても名前を変える事で同じとみなせる断片を探せるようになる。図 8
の二つの断片も字面は一致しないが書き換え後は同じ表現になる。
レジスタ再割り当て
サフィックス木が入力プログラムの相対表現に基づいて構
築されると、二つの断片が例え異なるレジスタを使用していても同じ繰り返しと
みなせるようになる。こうしてその断片を圧縮するためには、レジスタ再割り当
てをしてある断片を別なものと同じにしてやる必要がある。
分かりやすく言うと手続き P1 において断片 F1 が与えられ、手続き P2 におい
て断片 F2 が与えられたとき、レジスタ再割り当てはプログラムの意味は変えず
に、F2 が F1 と同じになるように P2 におけるレジスタ使用を変更しようとする
ことである。再割り当ては二つの断片を同一化できないこともある。というのも
コンパイラは実在するレジスタによる制約下で動作しなければならないからであ
る。本論文で再割り当てのために使用する戦略は存在範囲再配置と呼ばれるもの
である。
存在範囲再配置
存在範囲再配置と言うのは、グラフ塗り分けによるレジスタ
割り当てで使用されるのと同じツールをいくつか使用するレジスタ再割り当て方
法である。再割り当て処理は各手続きに対して Chaitin 型の妨害グラフを構築し
て操作することで、個々の存在範囲を粒度として行われる。本圧縮機構は入力に
レジスタ割り当てが完了してから動作するので、全てのグラフはそれぞれの存在
範囲に割り当てられた物理レジスタごとに異なる色で塗り分けられている。この
手法を説明するための各表現を図 10に示す。
図 11の例を解説する。断片 F2 を断片 F1 と同一にするためにそこで使われて
いるレジスタを再割り当てしたいとする。この例では F1 の rk に対応する F2 の
rj に注目する。図 11で LR(Q) と言う断片は手続き X の妨害グラフにおける rk
への参照を含む存在範囲であり、LR(S) は手続き Y の妨害グラフにおける rj へ
の参照を含む存在範囲である。
Rk に塗り直したい存在範囲 LR(S) が与えられたとき、再帰的なアルゴ リズム
を利用する。まず初めに、妨害グラフを用いて単に LR(S) を rk に塗り替えるこ
26
notation
interpretation
F
!"#$%
IGP
P Q
LRQ
COLOR LRQ 図 10 存在範囲再配置の説明における各表現
図 11 再配置の例
27
図 12 再割り当て
とが問題ないかを調べる。この段階を単純再割り当てと呼ぶ。もしこれが成功し
たらプロセスは終了する。失敗した場合 LR(S) に隣接する全ての rk を新たな色
に塗り直す。これで単純再割り当てが可能になる。この段階は隣接障害回避と呼
ぶ。これも失敗した場合は見越しで LR(S) を rk に塗り直し 、再帰呼び出しで隣
接する rk の領域を rj とか他の空いている色に塗り直す。再割り当てアルゴ リズ
ムの全体は図 12に示す。
単純再割り当ては次のように動作する。LR(S) を rj から rk に塗り直す正当性
を確かめるために F2 を含む手続きの妨害グラフを参照して、LR(S) に干渉する
rk で塗られた範囲 LR(T) が存在するかを調べる。このような LR(T) が存在しな
ければ LR(S) は安全に rj から rk に塗り直せる。
失敗した場合図 13にアルゴリズムを示している隣接障害回避を試みる。ここで
は rk に塗られていて LR(S) に干渉しているような存在範囲 LR(T) 全てに対して
繰り返される。それぞれの LR(T) に対して LR(T) に干渉しない領域でしか使わ
れていない rq を選んでそれに塗り直そうと試みる。もしこのような LR(T) が全
て安全に塗り直せたら、LR(S) は rk に塗り直せる。
どちらの方法も失敗した場合は再帰的な段階に進む。目的の存在範囲 LR(S) は
rj から rk に塗り直され、再帰呼び出しによって rk である隣接領域が rj とか他の
28
図 13 隣接障害回避
図 14 再帰処理
29
空いている色で塗り直される。最悪の場合再帰的な再割り当ては rk の領域と rj
の領域を完全に交換するだけになることもある。
手続き中の一連の存在範囲再配置操作が行われるときは、一連の変更操作の結
果はやり直しが効かないので注意する必要がある。結果として毎回存在範囲の再
割り当てが行われるたびに操作を wired-color 表に記録しておく。一連の存在範
囲再配置処理を進める上で、変更をしようとする前には wired-color 表をチェック
して、もしすでにその存在範囲が変更済みであれば再配置処理自体を中止する。
5.4.3
プロファイルに基づく選択
ここまで述べてきた圧縮方法は、実行頻度に関する情報なしに手当たり次第変
換を適用するものである。もし圧縮機構が選択した断片が重要な内部ループの中
にあった場合、プログラムの実行時間の大幅な増大をもたらすこともある。
この問題を解決するために圧縮機構を可能ならプロファイル情報を利用して圧
縮過程を誘導するように調整する。コンパイラはプログラム中の関数の実行命令
数に基づくプロファイル情報を利用できる。各関数 F に対してコンパイラは F の
プログラム上の命令数と実行される命令数の比率 Rf を計算する。N 関数の全て
の情報が与えられると、コンパイラは全比率の中で Q 番目の比率の値を選び出
す。
（標準では Q の値は 0.85 である。）これをカットオフ比率と呼ぶ。つまりコ
ンパイラは全体の比率の中で85%より大きな Rj をとる関数 J を選択する。こうし
て選ばれたカットオフ比率が圧縮過程で利用される。カットオフ比率より大きな
比率の関数に対しては全ての断片の圧縮を試みるのである。基本ブロックに対し
てプロファイル情報の荒さにもかかわらず、5.5.4 節で結果を述べるが実験による
とこの方法はかなり効果的であった。
5.5
実験
本章で述べてきた手法の概略を研究用のコンパイラに実装して、一連の評価用
プログラムでテストした。この実験の結果を以下に示す。
30
/012
Adpcm
-.
)*+,PCM
%&'(
Shorten
Gsm
Gzip
Mpeg2dec
Mpeg2enc
Jpeg
gs
!"#$
GSM
MPEG-2
MPEG-2
SPEC95
図 15 評価プログラム
5.5.1
評価プログラム
本研究で使用したのは信号処理や音声、動画などの符号化および圧縮のための
C 言語のプログラムである。表 15に各プログラムの機能の概略を述べ、表 16に
機能数とか命令数、実行時の大まかな命令数を含むプログラムの特色を示す。実
験時間の制約で一部のプログラムではデータの大きさを縮小している。
研究用のコンパイラは RISC のアセンブラに似た低レベルのレジスタ転送中間
言語を生成できる C のフロントエンドを備えている。中間言語レベルでのコンパ
イラの操作やコード サイズ、実行時の命令数などの結果は中間言語表現で出力さ
れる。最適化は次のような段階を備えている。変数によるコード 移動、強度縮小、
条件定数伝播、コピー伝播、ローカル変数順序付け、無効コード 削除、不要コン
トロールフロー除去、レジスタ割り当てである。本研究ではインライン展開とか
ループ展開のようなコードサイズを増やすような最適化は解除した。レジスタ割
り当て機構は Chaitin 型のグラフ塗り分け割り当て機構で、レジスタをラウンド
ロビンで選択し再割り当てをサポートしている。対象としているのは 32 の整数
レジスタと 32 の浮動小数点レジスタを備えたアーキテクチャーである。コード
圧縮は最終段階でレジスタ割り当ての次に行われる。標準では全ての最適化を入
力プログラムのコンパイル時に可能にした。最適化機能を利用しない状態を再現
するためにはレジスタ割り当て後にローカル変数の順序付けだけを行った。
31
Adpcm
Fftn
Shorten
Gsm
Gzip
Mpeg2dec
Mpeg2enc
Jpeg
gs
6
356
12.4M
8
3,689
1.1M
56
7,274
2.0M
95
12,081
85.6M
98
11,511
1.8M
114
11,218
10.2M
210
16,884 205.9M
380
36,959 681.2M
1,142
68,590
48.2M
図 16 プログラム特性
5.5.2
結果
表 17は 3 つの戦略でコード 圧縮を行った際の実験結果の比較である。最初の手
法は厳密に字面が一致する命令パターンマッチングだけを利用する方法である。
第二の手法は分岐を相対位置で扱う方法である。第三の手法は相対レジスタで
5.4.2 節で述べたようにレジスタの再割り当てを含めてレジスタの抽象化をした
パターンマッチングを利用する方法である。初めの 3 つの欄はそれぞれの方法で
のコード サイズの縮小率を、次の 3 つの欄は実行時の命令数の増加率を表してい
る。全ての数値は全最適化を施して圧縮しなかった場合を基準とした割合である。
結果はレジスタ抽象化を含む圧縮が大幅に圧縮率を高め、平均5% 、gsm におい
ては14.8%の圧縮率を示した。一方他の手法では平均1%前後の圧縮しか得られな
かった。コード 圧縮によって得られる空間は大抵の場合実行される命令数の増加
とおおよそ等しくなる。従って、この種の最適化は実行速度が優先される場合に
は望ましくない。5.5.4 節ではプロファイル情報を使うことでこの制約を減らせる
ことを示す。
まとめると、本実験の結果この段階の圧縮方法はレジスタ使用の違いを考慮に
入れれば現在の命令セットアーキテクチャーに対しても効果的である。
32
図 17 結果
5.5.3
コード 圧縮と既存の最適化との相互作用
図 18はコード 圧縮で得られる空間節約量と既存の最適化で得られる節約量の比
較である。3 つの欄は全て最適化を掛けない状態でのコード サイズに対する比率
である。最初の欄は最適化のみによる圧縮率である。2 つ目は圧縮のみによるも
のであり 3 つ目が最適化された入力プログラムを圧縮したものである。
図 18の 2 つめの欄を見るとコード 圧縮は最適化されていないプログラムに対
する方が高い圧縮率を示す。しかし一例を除いて最適化とコード 圧縮は組み合わ
せた方が単体の場合よりも良い結果となった。このことはどちらの技術も他方が
適用されない機会をりようしていると示唆されていると考えられる。従ってコー
ド サイズが重要なアプリケーションではコンパイラは既存の最適かもコード 圧縮
も利用すべきである。
想像どおり、コード 圧縮の効果と言うのは最適化過程を経てえられるコードの
形に大きく依存する。特にレジスタ割り当てのわずかな違いが時には圧縮率に関
して無視できない違いになることが分かった。
まとめるともっと細かく設計されたコンパイラの出力に適用することでコード
圧縮の結果はもっと大きく改善できると期待できる。ローカルレジスタ割り当て
後の単純なコード 生成がもっとたくさんの長い断片の繰り返しを作り出せるかも
しれない。
33
20.00% 3.45%
Adpcm
5.33% 8.34%
Fftn
16.37% 2.76%
Shorten
21.75% 8.23%
Gzip
16.14% 14.29%
Gsm
15.89% 7.98%
Mpeg2dec
17.11% 6.96%
Mpeg2enc
Jpeg
26.65% 9.70%
Gs
27.76% 9.47%
18.56% 7.91%
22.53%
6.27%
17.69%
24.40%
28.58%
19.50%
20.49%
31.22%
31.61%
22.48%
図 18 相互作用
5.5.4
プロファイル情報の利用
図 19は繰り返し選択時に 5.4.3 節で述べたプロファイル情報を組み合わせた結
果を示している。数値はレジスタ再配置を利用した圧縮のものである。
（ Adpcm や tn などの）少数の関数で構成されるプログラムの場合は、ほと
んど変化は見られない。領域節約量はプロファイルを使わない場合と変わらない
し実行命令数もそうである。これはこうしたプログラムがわずかな関数しかもた
ず扱いの難しいはっきりとした違いがあると言う事実によるようである。しかし
もっと大規模なプログラムでは結果は素晴らしいものである。実行命令数の増加
（プロファイルを使
は最大でも0.4%でその際の圧縮率は標準の80%以上であった。
わない場合の平均4.8%に比べて平均で3.9%であった。）こうした結果から、プロ
ファイルのカットオフ率を変える事でコンパイラやユーザーは実行速度とコード
サイズの間のトレード オフを大きく制御することができると考えられる。
34
Adpcm
3.16%
7.01%
Fftn
1.00%
0.01%
Shorten
0.85%
0.00%
Gzip
2.11%
0.00%
Gsm
12.30%
0.35%
Mpeg2dec
2.96%
0.08%
Mpeg2enc
3.24%
0.30%
Jpeg
5.03%
0.00%
Gs
4.33%
0.02%
3.89%
0.86%
図 19 プロファイルに基づいた結果
35
図 20 所要時間
5.5.5
圧縮時間
本節では圧縮にかかる時間そのものに着目する。図 20はそれぞれのプログラムに
対するコード 圧縮形態毎の所要時間である。数値は毎秒処理できる命令数である。
システムは 150MHz の PentiumPro に 128MB のメモリを搭載して FreeBSD2.2.2
で動作するパソコン上で実行した。図の時間は入出力や CFG の作成、構文解析に
かかるものは含まず、入力プログラムを SSA 形式に変換する時間を含んでいる。
分岐相対のコード 圧縮は毎秒 11K 命令近くと非常に高速であることが分かる。
レジスタ相対方式はこれに比べてかなりの時間がかかることが分かる。これは妨
害グラフをプログラム中の各関数に対して作成して処理しなければならないから
であろう。平均で毎秒 1K 命令程度となっている。圧縮全体にかかる時間は充分
実用的で、プログラム全体をコンパイルして最適化するまでにわずかな時間しか
かかっていないことが分かる。
5.6
今後の拡張
もちろん本章で述べてきた圧縮機構は効果的であるが、更なる拡張の余地があ
る。本節では本手法の限界について触れ、将来の研究の方向性について論じたい。
定数抽象化
現在の実装では入力プログラムのサフィックス木を作る際に、物
理レジスタの抽象化のために再配置を行っている。サフィックス木を作る前に定
数利用の違い抽象化する大まかな手法がある。それは違いを吸収するために定数
を手続きが呼び出されるときに定数をレジスタに格納して渡すのである。図 21の
36
…Fragment F1…
ADD r1,r2r3
LOAD [r3] r4
ADDI 4,r4r4
ADD r5,r2 [r3]
STORE r4 [r3]
…
…Fragment F2…
ADD r1,r2r3
LOAD [r3] r4
ADDI 8,r4r4
ADD r5,r2 [r3]
STORE r4 [r3]
…
図 21 定数抽象化
…Fragment F1…
ADDI r1,99r2
SUB r3,r4r5
STORE r5 [r2]
…
…Fragment F2…
SUB r3,r4r5
ADDI r1,99r2
STORE r5 [r2]
…
図 22 命令並べ替え
例を見てみよう。
現在のシステムではこの断片を圧縮することはできない。なぜなら ADDI 命令
で使われる定数が異なるからである。1 つの解決法は ADDI 命令を ADD 命令に
変え、領域固有の定数を手続きが呼び出される前に読み込むことである。こうし
た機会を自動的に利用するためには多くの条件が必要である。実際どちらの断片
も呼び出す手続きに定数値を渡すための空いているレジスタが必要になる。
命令並べ替え
この種の圧縮を支えるパターンマッチング機構というのは命令
の順序に敏感である。もし二つの断片が同じ命令を、しかしわずかに実行順序が
違って（意味は同じであるにもかかわらず）実行するとしたら、サフィックス木
では両者は同一とはみなされない。
図??の例がそれを示している。二つの断片は同じ命令を実行している。しかし
命令の実行順序はわずかに違う。
（初めの二つの順序が入れ替わっている。）圧縮
機構は多少の順序の差は繰り返し断片を最適配置するときに許容できる。
この問題に対する 1 つの解法は、サフィックス木を作る前に基本ブロック内で
37
命令順序を標準に並べなおすことである。
（依存制約にはもちろん従わなければ
ならない。）これで不要な順序をなくすことが期待できる。もう 1 つの方法は特
定の基本ブロックに関しては複数の命令を 1 つの塊とみなしてサフィックス木を
構築することである。
レジスタ割り当て前の圧縮 レジスタ割り当てが（コード 溢れや物理レジスタ
の違い等）同一コードの探索課程を複雑にするので、中間言語が実レジスタでな
く仮想レジスタへの参照を含んでいる段階で、逆にレジスタ割り当て前に繰り返
しコードを圧縮する方法も考えられる。しかしレジスタ割り当て前に手続き抽出
を行うことは多くの問題を含んでいる。というのもレジスタ割り当てが手続き呼
び出し際に起こるパラメータの受け渡しをサポートする必要があるからである。
5.7
まとめと結論
本章ではサフィックス木に基づくコード 圧縮の解説と新たな拡張に対する評価
を行った。つまりコンパイラがどのように直接実行できる形式を保ったままより
小さなコードを作り上げるかを示した。多目的処理のためにコンパイル時にこの
種の領域最適化をするのは比較的重要ではないが、コードサイズがシステム全体
の価格に直接跳ね返る組み込み処理の為にプログラムをコンパイルするときには
非常に重要になる。
実験結果によればこの種のコード 圧縮は、かつての複雑な命令セットを持った
計算機のために研究されたにもかかわらず今日のコンパイラや命令セットに対し
ても十分機能する。コード 圧縮は既存の最適化技術とも他方の代わりとはならず
協調することも分かった。結果によれば存在範囲再配置と組み合わされた緩やか
なパターンマッチングはコード 圧縮の実質的な効果を高め、実験した評価プログ
ラムでは 1-5%の圧縮率の改善が見られた。最後に、圧縮段階でのプロファイル情
報の利用で、実行命令数の増加を大幅に抑えられは通常この種の方法に避けられ
ないものであったが、おかげでサイズも速度も同じくらい重要な場面でも使いや
すくなった。
38
6.
6.1
組み込み Java システム
導入
Java 言語というのは多くの場面で好んで使われているが、組み込みシステムで
の利用も考慮して設計されている。これは Java カード 仕様とか組み込み Java 仕
様と言った特別な API が使えることからも分かる。Java を使う最大の利点はこ
こでは可搬性である。これは Java のバイトコード の形式があらゆるサード パー
ティーの開発したサービスを Java 互換の組み込みシステムで利用できるように
なっていることで実現されている。
組み込みシステムは利用できるメモリの総量に強い制約があるので、実行でき
るプログラムのサイズが厳しく制限される。メモリの制約にはいくつもの理由が
ある。製品価格を下げる必要、消費電力を最小化する必要、実際に利用できる空
間が小さいことなどである。このため、組み込みプログラムは実行時に割り当て
られる分だけでなく、コード 自体が格納される領域分も含めて、可能な限りメモ
リ消費を抑えることが望ましい。プログラムの各機能に割り当てられる領域が少
なければ少ないほど 、多くの機能をシステムに付加できるからである。
Java のコード はかなり小さいが 、それでもプログラムはコード の繰り返しパ
ターンを含んでいる。このようなプログラムの格納サイズを小さくしなければな
らない場合には、圧縮と言うのが主な解決策として浮かんでくる。
データの圧縮は非常に広範な適用例があり、よく研究されている分野である。
昔からのやり方としてはプログラムの各部分をそれが必要になるときに解凍し
て、使い終われば破棄するという方法がある。しかしこの方法は普通組み込みシ
ステムにおいては使えない。まず、組み込みシステムにおいては単一のメソッド
を解凍するにも充分なメモリがないことが多い。例えば JavaRing のような既存
の JavaCard システムは 32K の ROM と 6K の RAM しかない。次に、そのよう
なコードブロックを解凍するのにかかる時間は、組み込みシステムが守らなけれ
ばならない時間制約を超えてしまう可能性がある。先の例でいえば、JavaCard の
ユーザー操作は 1 秒以内に完了しなければならない。
本章では時間制約を変えることなく空間を節約するための解決策を示す。ここ
39
では再帰的な命令列を新しい命令に要素化することを提案する。こうして命令
セットを拡張した Java 仮想機械上で実行可能なより小さなプログラムを作り出
す。新しい命令を既存の命令のマクロとして表現することで、仮想機械はこれら
のマクロ命令をサポートするように拡張するだけでよく、一つ一つのプログラム
に対する特別な命令をサポートする必要はない。この方法でプログラムサイズは
平均30%圧縮され、実行時の速度低下は30%を超えなかった。
本章は以下のように構成される。6.2 節では Java のプログラムの圧縮に適用で
きる様々な技術について論ずる。コードを 6.3 節の例に示すようにバイトコード
のマクロとして要素化する。6.4 節では実際の要素化のアルゴ リズムについて説
明する。6.5 節ではどのようにマクロをサポートする機能を仮想機械に実装した
かを述べる。得られた実験結果は 6.6 節に示す。最後に関連研究について 6.7 節
で述べ、6.8 節でまとめる。
6.2
Java
バイト コード の圧縮
Java のクラスファイルのサイズを小さくするのによく用いられるのは、重要で
ない情報を全て取り除いてしまうことである。しかしこの方法は組み込みシステ
ムの場合次の節で述べるようにあまり有効ではない。それでも標準的な圧縮方法
を使うことは 6.2.2 節で述べるように限られた範囲では可能である。圧縮する代
わりに標準の Java バイトコードは 6.2.3 節で述べるように再帰的な命令列を要素
化した表現が利用できる。しかし本当に代わりになるのは 6.2.4 節でのべるよう
に新しい命令を生成する場合だけである。
6.2.1
クラスファイルの縮小
Java はインターネットを通じてプラットフォームを選ばないプログラムの配布
手段として広まっている。その場合よく使われる Java クラスファイルの縮小手
段は事前にクラスファイルを、デバッグ情報を取り除いたり、Java クラスの内部
で名づけられている定数表現をより短い表現に置き換えたりして処理することで
ある。しかし組み込みシステムの場合はこうした前処理は冗長になる。これらの
情報の大半はクラスファイルが組み込みシステムで使われている内部表現に変換
40
されるときに分割される。つまりクラスファイルのサイズは些細なことなのであ
る。重要なのはプログラムがカードに転送されたときにどれだけのスペースを取
るかである。
デバッグ情報と全部ではないにしても定数情報の大半を削除することで、残る
のは Java プログラムのメソッド の定義をしている実際のバイトコードだけにな
る。コードのサイズを減らすもうひとつの手段は使用しないメソッドを削除する
ことである。しかし残されたメソッドのバイトコードはやはりスペースを占有す
るので、コード 圧縮方法とは方向の違う手段だと考えられる。
6.2.2
基本ブロック圧縮
単純な Java クラスファイルの操作の次に、よく使われる圧縮方法にハフマン
符号化法とか LempelZiv 圧縮法といった単語列圧縮方法がある。プログラム全体
は圧縮された形で保存され、ROM から実行時に各部分が必要に応じて RAM に
転送されるときに解凍される。しかし組み込みシステムでは限られたメモリ資源
しかないので単一メソッドの解凍すら不可能な場合も考えられる。プログラムの
全体を RAM に格納するより、コード の各基本ブロックに個別にストリーム圧縮
法を適用する。基本ブロックの命令は順番に利用されるので、RAM に格納する
ことなく調節された JVM で実行時に解凍できる。こうした一般的な圧縮アルゴ
リズムは、プログラム中に見られる種のパターンに対しては最適でないかもしれ
ないが良く知られ簡単に実装できる。
けれども、この解決法は面白そうではあるが目的を十分には達成できなさそう
である。まず、ストリーム圧縮法は多くの小さな個別ブロックの圧縮には適して
いないので、限られた圧縮率しか得られないと予想される。次に各基本ブロック
を解凍するのにかなりのオーバーヘッドが生じて、システム全体の速度を許容で
きないほど低下させる恐れもある。
6.2.3
メソッド とサブルーチン
ほとんどの Java プログラムでは表現の繰り返し出現が含まれる。簡単な例と
して、クラスを通して操作されるある目的フィールドが 、毎回同じ操作でアクセ
41
スされる場合を考える。最適化コンパイラは共通部分表現の削除によってこの冗
長性を除去できるが、それはこうした表現が全部同じ値だと計算された場合だけ
である。普通、バイトコードのプログラムは異なる値をとる同じ命令列の出現の
繰り返しを含んでいる。
JVM に変更を加えずにこうしたコードの複製なくす方法は、繰り返し命令列を
定義する新たなメソッドを利用することである。同じクラスで様々な場所からア
クセスされる特別な命令列は、新たなメソッドに置き換えられる。各命令列はメ
ソッド の呼び出しに置き換えられる。これは実行システムには変更を加える必要
はないが、メソッドを定義するのに領域を無駄にし 、
（ Java クラスファイルに 26
バイト必要である。）各命令列呼び出し部に 3 バイト必要になる。さらにローカル
な状態変更があると明確に前後に伝えるのにかなりの時間と領域を必要とする。
命令列の定義にサブルーチンを使えば局所状態は共有できるので、領域の無駄
は各サブルーチンの定義あたり 3 から４バイトに制限できる。しかしサブルーチ
ンは手続き内部のもので使える場所が限られるため、この方法は目的の為に充分
ではない。
6.2.4
命令セット 拡張
Java に限った場合の解決法として、仮想機械の命令セットを拡張して再帰的な
命令列を置換できる命令を加えることが出来る。Java のバイトコードは一般的で
特定のアプリケーションに限った設計はされていない。よく使われる命令には特
殊なものがあって例えば初めのいくつかの局所変数にアクセスするような命令で
ある。しかし似たようなオブジェクトを操作する命令の特別なバージョンを用意
することは出来ない。こうした命令はプログラムに固有の定数プールを通じて名
前を参照するからである。
JVM というのは組み込みシステムごとに用意されるので、JVM が標準の Java
バイトコードを実行できる限り新たな機能を追加しても構わない。しかし新しい
命令の追加はインタープリターの改変に手間がかかりまた違う命令を使用するこ
とになれば新たに書き直さなければならない。さらによく使われる命令には、特
にフィールド 操作やメソッド 呼び出しではその命令が属するクラスの定数プール
42
に依存した引数をとることがある。ここで定数プールはクラス間のダ イナミック
リンクとして働き、引数は他のクラスへの絶対位置というより定数プールのシン
ボルインデックスとなる。こうした引数を正しく解決できなければならない。
一方、この方法はもっと一般的な方法でも実現できる。仮想機械がクラスファ
イルで定義された新しい命令を実行できるように拡張するのである。これらのマ
クロ命令はバイトコードの命令からなり、コード 中の共通の命令列を置き換える。
標準命令セットに含まれないあらゆる命令は変更可能で、実行中のプログラム毎
に特定された表で定義されると仮定している。マクロ命令はメモリ上ではわずか
な負担だけで実行時のシステムに格納できる。各マクロ命令はプログラム毎に特
別で、特別なクラスファイルの定数プールと対応して定義できる。この方法では、
追加できる命令の数は標準命令セットでは使われていない命令の数で制限される。
この最後の方法が最も有望である。時間上も領域上も負荷はわずかであり、簡
単に実装できるし 、かなりの圧縮が達成できる。本章の残りはこの方法の実装と
実験について述べる。
6.3
簡単な例
本研究の方法は、繰り返される命令列をまとめて、結果をマクロを使って書き
換えることである。
例として次のような Java クラスを使う。Point というクラスは幾何学的な点を
表現していて、座標系の中心からの距離を計算するメソッドを備えている。Box
というクラスは単純に中身への参照だけを備えている。対応するバイトコードプ
ログラムはその次に示してある。両クラスの生成子は Java コンパイラによって
自動的に導入される。
public class Point {
public int x, y;
public int dist() {
retunr Z.intSqrt((x*x)+(y*y));
}
}
43
public class Box {
public Object content;
}
Method int dist()
0 aload_0
1 getfield #4 <Field Point.x I>
4 aload_0
5 getfield #4 <Field Point.x I>
8 imul
9 aload_0
10 getfield #7 <Field Point.y I>
13 aload_0
14 getfield #7 <Field Point.y I>
17 imul
18 iadd
19 invokestatic #6 <Method Z.intSqrt(I)I>
22 ireturn
Method Point()
0 aload_0
1 invokenonvirtual #5 <Method java.lang.Object.<init>()V>
4 return
Method Box()
0 aload_0
1 invokenonvirtual #5 <Method java.lang.Object.<init>()V>
4 return
このバ イトコードプ ログラムでは 、明らかなまとめ上げのチャンスがある。
Point.x フィールドにアクセスするために Point の実体がスタックに読み込まれ、
geteld 命令が値を抽出するために使用され 、次の命令列の繰り返しが 2 つ与え
られる。
44
0 aload_0
1 getfield #4 <Field Point.x I>
さらにど ちらのクラスも Object の生成子の呼び出しからなる標準の生成子か
ら拡張されている。
0 aload_0
1 invokenonvirtual #5 <Method java.lang.Object.<init>()V>
4 return
プログラム中の標準の生成子は全く同じ実体を持ちまとめるのには理想的な
チャンスを示している。
こうした特定のプログラム中に繰り返し使われる標準命令の列を見つけるたび
に、新しい命令に置き換える。次のソースはこのプログラムをまとめた結果得ら
れるバイトコードプログラムで、マクロに対応する表を一緒に示してある。フィー
ルドへのアクセスのための繰り返し使われる命令の列は、生成子の実体と同様に
マクロ命令にまとめられている。
Method int dist()
0 Macro #204
1 Macro #204
2 imul
3 Macro #205
4 Macro #205
5 imul
6 iadd
7 invokestatic #6 <Method Z.intSqrt(I)I>
10 ireturn
Method Point()
0 Macro #206
Method Box()
45
0 Macro #206
Macro instruction 204:
0 aload_0
1 getfield #4 <Field Point.x I>
Macro instruction 205:
0 aload_0
1 getfield #7 <Field Point.y I>
Macro instruction 206:
0 aload_0
1 invokenonvirtual #5 <Method java.lang.Objecti.<init>()V>
6.4
ファクタリゼイション
それでは、Java のバイトコードを一連のパターンをまとめた等価なプログラム
に変換するアルゴ リズムを示そう。理想的なパターンセットを計算するのは NP
完全問題になるので、この章で示すアルゴ リズムは多項式時間で計算できる準理
想的なパターンセットを計算するものとする。
概念は、繰り返される操作が単一の命令に吸い出されるというものである。こ
うしたバイトコード 命令の列はそれぞれパターンとして示され、各パターンは対
応するバイトコード 列と同じ働きをするものとする。パターンに関してプログラ
ムをまとめると、より小さなプログラムが生まれる。パターンが出現するたびに
そのパターンの命令を表現する新しい命令に置き換えられるからである。置換可
能なパターンの出現を全て集めたものは出現グループと呼ばれる。
まとめ上げは 3 段階で行われる。まず、繰り返される命令列をまとめるために
パターンが作り出される。次に、こうしたパターンの中でマクロ表現が出来ない
ものが取り除かれる。最後に、小さなバイトコードを生成するためにこうしたパ
ターンに関してバイトコードがまとめ上げられる。
46
6.4.1
パターン生成
命令はまず、分岐情報（その命令をターゲットとする命令）を保った数値情報
に抽象化される。これらの数値は、全ての命令を任意の順番に並べなおして異な
る引数を取る命令は異なるようにして決められる。定数は比較する前に調べるの
で、異なるクラスの命令も正確に比較される。
プログラムをまとめるパターンセットを把握するために、出現グループの最大
セットが用意される。まず、長さ 1 のグループが同じ命令全てに対して作られ、
こうしたグループが順番に伸びていくか、新しいグループに分けられて拡張され
ていく。もしグループの最後の命令に続く命令が全て同じなら、グループは 1 命
令分長くなる。そうでなければ 、それぞれの末尾の命令毎に新しいグループが構
成される。
延長された出現グループは自分自身に重なるかもしれない。つまりグループの
ある出現が他の出現と重なる可能性がある。こうした場合、重なった後ろ側の出
現は次の出現を調べる前に取り除かれる。こうして、出現グループから除去され
るパターンは出来る限り少なくなるようにされている。全ての出現グループが確
認されると、他のグループによって完全にカバーされているグループはそこから
取り除かれる。
6.4.2
パターン枝刈
ある種のまとめられない命令がパターンに含まれないように、またグループの
境界を越えた分岐命令が出現しないように出現グループを調査する。これには 2
つの段階が含まれる。まず、まとめられない命令とグループ外への分岐命令が扱
われ、それからグループ内への分岐が調べられる。
命令 tabelswitch,lookupswitch,jsr と ret はまとめられない命令と見なしている。
switch 命令はアライメントの制約でマクロ内に配置するのは難しく、またサブ
ルーチン命令は手続き間の制御フローに問題を起こすかもしれないからである。
こうしたタイプの命令はあまり頻繁に出現しないので、無理にこれらをまとめて
複雑にする価値はないものと考える。
まとめられない命令はパターンを 2 つの新しいパターンに分割することでパ
47
ターンから取り除かれ、出現グループは順次分割される。同じように、グループ
外への分岐が残っているパターンも、2 つの新しいパターンに分割することで分岐
命令はグループから取り除かれる。この段階を簡単にするために、パターン中に
は前へ戻る分岐を許さないものとする。もともとほとんどの分岐は if 文と break
文からなる先へ進むものである。分岐を後方から調べることで、パターンの分割
が新たなグループ境界をまたぐ分岐を生み出さないことが保証できる。
それからグループ内への分岐を調べる。パターンの全てに出現する外部への分
岐と対照的に、内部への分岐は単一の分岐命令の結果として生じ 、グループ全体
では共有されない事が多い。そこで、パターンのグループ全体ではなくて実際に
分岐の対象となった出現のみを取り除くことにする。そうでなければ分岐の対象
となる命令とそれに続く命令でパターンを分割することになるが、これはパター
ン間の分岐が生じてないことを保証するために余分なチェックを必要とすること
になる。例外処理の最初の命令や、例外が含まれるコード 領域の最初と最後の命
令はグループ内への分岐対象と同じように扱われる。こうした処理の後で、完全
に他のグループにカバーされているグループとサイズが 1 のグループが取り除か
れる。
6.4.3
パターン適用
パターンセットを計算した後、マクロ命令の生成を始める。マクロは最も節約
できる出現グループから、新しいマクロを生成する余地がなくなるか、領域を節
約できる出現グループがなくなるまで、全て選択していく、貪欲なアルゴ リズム
で生成される。各出現部の最初の命令が、何命令をまとめたかと言う情報と共に
マクロに置き換えられる。部分的に、あるいは完全にカバーされる出現は取り除
かれるが、このパターン全体をカバーする出現は残される。完全にカバーされる
出現はそれぞれのグループから取り除かれるが、グループが新しいマクロ内の出
現を含んでいるかもしれない。そのグループの出現と最初の命令が同じ出現は、
それより短い場合はマクロを、長い場合はマクロ命令を指し示す必要がある。
命令セットに含まれる未使用命令の数が 、新たなマクロ命令を作れる数を決
める。標準の Java 命令セットは 203 の命令を含んでいる。マクロの終端を表現
48
するの 1 つ命令が必要なので 、最大 52 個の 1 バイトマクロ命令が利用できる。
JavaCard 命令セットの場合 103 命令しか使用していないので、最大 152 個の単
バイトマクロ命令が利用できることになる。
マクロを単バイトで表現するのは単純で負荷もほとんどかからないが、定義で
きるマクロの数は JVM の命令セットで未使用な命令の数に制限される。このた
め、2 バイト命令長のマクロを定義したい場合も考えられる。このやり方は 1 バ
イト命令を使う場合ほど容量を削減できないが、それでも場合によってはやる価
値がある。つまり出現頻度の小さなものを 2 バイトの命令に選ぶことで、削減で
きる容量の損失は最小に抑えられる。
2 バイトマクロの先頭バイトは命令符号で、後続バイトを既存の単バイトマク
ロの表に対する位置指定とすることで、こうして使われるそれぞれの命令に対し
て 255 のマクロを定義する余地が出来る。
マクロは定義から再帰的ではないので、JVM に対して必要な修正を最小限に
するために、まとめるときに手続き間のマクロの入れ子の最大値を計算する。ま
とめられたコードは付録節 A に示すように 2 つの属性に分けて保存される。オリ
ジナルのコード も保存されていて、まとめたコード をサポートしていない JVM
でもプログラムは実行できる。
6.5
拡張 JVM の実装
この節では拡張命令セットで表現された圧縮プログラムを実行できるように、
標準 JVM を拡張する方法について説明する。拡張命令は既存命令のマクロ形式
で表現される。拡張 JVM ではマクロ化されたクラスファイルを読み込んで実行
できなければならない。まずはマクロがどのように表現されるかを 6.5.1 節で述
べ、マクロをサポートするために JVM の主ループに必要な修正の詳細を 6.5.2 節
で述べる。
6.5.1
マクロ表現
標準 JVM をマクロ命令の実行が出来るように拡張する。JVM で実行する前
に、プログラムはマクロ命令セットとともにそれを使った修正コードにまとめら
49
れる。マクロは基本的に 3 つの値で定義される。命令コードと実体、実体内で使
われる定数を定義するクラスである。マクロの実体は、macro_end という特別な
命令で終わるコードブロックである。その中には他のマクロ命令を含んでいるか
もしれない。マクロ命令セットは全クラスに公開されている。定数への参照は全
て、それぞれのマクロに個別に記された特定のクラスの定数プールを参照する。
マクロは、どんな圧縮プログラムのマクロも修正されたインタープリターが利
用できるように、標準ファイル形式で保存される。参考に形式を付録 A に示す。
圧縮されたプログラムが組み込みシステムに転送されるときには、マクロも転送
されなければならない。しかし必要な情報はすでにプログラムのクラスファイル
に記述されているので自動的に行うことが出来る。組み込みシステムの拡張 JVM
が起動されると、圧縮バイトコードプログラムとマクロ定義は、JVM で使用さ
れる内部形式で必要な場所に用意される。
6.5.2
JVM
主ループ修正
JVM がマクロをサポートするように拡張するのは簡単で、一度変更するだけ
である。この変更は通常のメソッド のコードとマクロに格納されたコードを混在
させて実行できるようにするものである。マクロ命令は標準命令と同じ形式で表
現されるので、拡張されたインタープリターはあらゆる圧縮プログラムを実行で
きる。
スタックフレームを呼び出すメソッドは、マクロ呼び出しの為に固定長のプロ
グラムカウンタースタックを含まなければならない。マクロは再帰的ではないの
で、スタックの最大の深さは、圧縮アルゴリズムによってマクロセットと共に計
算できる。マクロ命令が呼び出されると、プログラムカウンターの現在値がマク
ロスタックに押し込まれる。その後、プログラムポインターが実行されるマクロ
の実体の先頭命令を指すように変更される。そこからマクロは、復帰命令である
macro_end が実行されるか、例外が発生するか、現在のメソッドから復帰される
まで実行される。
終端命令が実行されるとプログラムカウンターの値はスタックの先頭の値に戻
され、次の命令から実行が再開される。マクロ実行中に復帰が生じた場合は、制
50
御は呼び出し側に戻り、マクロスタックに格納されたプログラムカウンターを全
て破棄して現在のスタックフレームがスタックから抜き出される。同じように、
マクロの実行中に例外が発生した場合は、プログラムカウンタースタックの全体
が抜き出され、カウンター自体はスタックから抜き出された最後の値に戻される。
そして、制御は直接適切な例外処理に渡される。例外処理の選択は現在のプログ
ラムカウンターの値に対応する例外領域のレイアウトで決まる。各領域の大きさ
は、圧縮アルゴ リズムによってコード 領域が単独命令に置換されるときに縮小さ
れるので、正しい例外処理が自動的に呼び出される。
マクロ実体内からの定数への参照は、6.4 節で述べたように特定のクラスに関
しては決定されている。もし定数が組み込みシステムへの転送段階で決定される
のなら、それはこの特定のクラスに関して行われる。そうでなければ 、何か他の
クラスの定数プールに関して決定されなければならない定数を含むマクロを実行
している間、その定数プールへの道を残しておかなければならない。現在の定数
プールというのはマクロを呼び出すときに、プログラムカウンターに関して行わ
れるのと同様にスタックに保存できる。
参考までに、本節で述べた主ループのインタープリターに関する修正項目を付
録節 B に図解しておく。
6.6
性能評価
標準 Java クラスファイルの圧縮と、Harissa 環境におけるマクロをサポートし
た拡張 JVM を実装した。Harissa 環境と言うのは、Java の最適化コンパイラと
インタープリターを統合した環境で、インタープリターは動的に読み込まれるプ
ログラムの実行を可能にしている。
圧縮アルゴ リズムの効果と生成されたプログラムの実行速度を計るために、圧
縮アルゴ リズムを次のプログラムパッケージに対してテストした。
JavaCard library: JavaCard の参考実装から JavaCard2.0 のライブラリク
ラス。ライブラリは通常全ての JavaCard システムに提供されるので理想的
な圧縮対象となる。
51
図 23 バイトコード サイズ
JavaCard applets: JavaCard の参考実装から提供されている JavaPurse ア
プレットとプラットフォーム非依存の Visa Card version1.0 アプレット提供
者向けの実装。
JavaCard library+JavaCard applets: JavaCard アプレットのクラスファイ
ルと JavaCard2.0 のライブラリクラス。
JDK Applets: JDK1.0.2 に同梱されるデモンストレーションアプレット。
CaeineMarks: Java 向けに設計されたマイクロベンチマークセット。
Javac: JavaSoft の JDK1.0.2Java コンパイラ。
Compactor+Cream: Cream バイトコード 最適化機構と統合された圧縮プロ
グラム自体。
この中で、前半 3 つは JavaCard の命令セットのみを使い、後半は Java 命令
セット全体を使用した。図 23はバイトコードのサイズを圧縮の前後でマクロ定義
コードを含む場合と含まない場合をバイト単位で示したものである。平均メソッ
ド サイズも、単バイトマクロのみを使用して得られた全体のサイズと共に示して
ある。今回のテストではマクロスタックの入れ子の最大値は 4 を超えることはな
かったし 、最長圧縮過程でも 200MHz の UltraSparc で 15 分以内に実行できた。
（ 圧縮はプログラムを組み込みシステムに転送する前に 1 度だけ行えばよい。）
52
図 24 圧縮率グラフ
個々のメソッドを通常の圧縮アルゴリズムで圧縮した場合に見込まれる圧縮量
と、今回の方法で得られた圧縮量を比較する為に、得られた圧縮量を Unix の標
準圧縮ツールである gzip を使った 2 通りの場合と比べてみた。JVM の未圧縮の
メソッドに gzip を適用する為には、各メソッドは共通の辞書を使って個別に圧縮
されなければならない。この方法で得られる圧縮量を見積もる為に、gzip の圧縮
率を 2 つの異なる方法で計った。局所での圧縮量は、各メソッドのバイトコード
を個別に圧縮して得られる圧縮量からファイルオーバーヘッドとして 20 バイト
を引いたものである。全体の圧縮量は、全メソッド のバイトコードを 1 つのファ
イルとして圧縮して得られるものである。共通の辞書を使った圧縮に基づくアル
ゴ リズムは、小さなデータのビットに使われた場合この 2 つの値の間になると仮
定した。圧縮率は図 24に示してある。
マクロを使った実行時の速度制約を見積もる為には、Pentium（ DELL の 100MHz
の Pentium 機）と SPARC（ SPARC ステーション 5 ）の両方で 2 つのテストを
行った。Harissa インタープリターの制約から、JavaCard アプレットに関しては
テストが出来なかった。HarissaJVM は Pentium 機の gcc と SPARC の Sun の商
用 cc コンパイラ（ SPARC 上で cc を使ったコンパイルは未圧縮で最良の実行速
度性能を示す。）を使ってコンパイルした。最初のテストは圧縮された Javac コ
ンパイラの性能評価である。これは組み込み機器で使用されそうなプログラムで
はないとは言え、様々なデータを扱うタスクを実行する巨大で複雑なアプリケー
53
図 25 マクロによる速度低下
ションである。結果は図 25に示してある。実質的にはほとんど速度低下は見られ
ない。圧縮コードを扱うコンパイルタスクに 2,3%の遅延が見られるだけである。
第 2 のテストは CaeineMarks ベンチマークである。このセットに含まれるテス
トは、きわめて小さなベンチマーク（例えば tight-loop などは特別な命令だけを
テストする。）であるので、圧縮コード のスピードに関しては最悪時のテストに
なると仮定している。ここでは、Pentium 機で 19% 、SPARC で 27%という目立っ
た速度低下を観察した。しかしこれらの数値は許容範囲内にあると考える。
圧縮アルゴ リズムは明らかに、マクロ用に 100 以上の命令を用意できると言う
性質を持った JavaCard 命令セットにおいて、最良の働きが出来る。それにもか
かわらず、完全な Java バイトコード 命令セットにおいてもほぼ同等の性能が得ら
れた。表 6.1 の右端の欄から分かるように、2 バイトのマクロはここで平均5%の
改善を示す。
生成されたマクロを調べると、平均マクロ長は 3 バイト（中央値は 2 ）で各マ
クロは平均 9 回使用されている。ほとんどのテストで先頭の 8 個の局所変数にア
クセスする命令が単バイトのマクロに圧縮された。同様に、java.lang.Object の
生成子を呼び出す命令が大半のケースで圧縮されている。最後に各クラスファイ
ルセットに固有のフィールドにアクセスする場合は全て圧縮された。
こうした結果は、既存の JVM 命令セットをマクロ命令を使用して得られたの
と同程度のコードサイズの縮小が得られるように最適化する指標となる。しかし 、
マクロ命令はプログラムの定数プールに対応していて、固定された命令セットで
は対応できない点である。さらに、固定された命令を増やすことは、マクロ命令
を使った方法の効果を減じてしまう。それでも、わずかに異なった命令セットと
言うのは Java プログラムをはるかに縮小できる表現となる可能性がある。この
点は今後の課題である。
54
6.7
結論と今後の課題
Java バイトコードに対する圧縮を実装した。これはかなり大きなプログラムま
で扱え、バイトコード 全体のサイズを、時には gzip 以上であるおよそ30%圧縮で
きる。
現在、マクロが固定長の命令（マクロも含めて）を引数として利用できるよう
にする価値があるかを調査中である。命令列の繰り返しを示すパターンを保持す
るよりも、マクロの他の実体でも使える命令の数でパラメータ化する。設計上の
選択肢がいくつかある。例えば、複数の引数を許可するのか、引数に複数の命令を
許可するのかと言ったものである。パラメータ化されたマクロの複雑な書式をサ
ポートするもっと複雑な設計は、性能低下を招く複雑な実装になってしまうかも
知れない。単純な設計は効率的かもしれないが、本当に役立つマクロのパラメー
タ化をサポートするほど改良できないかも知れない。
6.8
付録 A
この節では、Java クラスファイルにマクロを格納するために提案された、正確
な標準配置について説明する。それぞれの圧縮されたクラスファイルは、圧縮さ
れていないオリジナルコードに加えて 2 つの新しい属性を持つ。圧縮されたコー
ド と、コードが圧縮されたマクロのセットである。バイトコードが組み込みシス
テムに転送されるときは、転送機構が組み込み JVM の能力に基づいてどちらの
属性を利用するかを選択する。
クラスファイルでは、圧縮されたバイトコードは IRISA.Macrocode と言う名
前の標準属性とよく似た属性に格納される。同様にマクロを定義するコードは後
述するように IRISA.Macrodef と名づけられた属性に格納される。この属性には、
マクロの最大の入れ子の深さと、定義するマクロの数と、マクロ定義の配列が含
まれている。各マクロは（後述の書式で定義される）1 バイト型のタグと定数を
決定する為のクラス、そしてコードのバイト列で定義される。命令 255 は、実装
仕様によって必要になる場合の為に、コード 配列を終了させる印（ macro_end ）
の領域として予約されている。
55
IRISA_Macrofdef_attribute {
u2 attribute_name_index;
u4 attribute_length;
u1 max_netsting;
u2 macro_table_length;
{ u1 type_tag;
union
{
{ u1 macro_code; } simple;
{ u2 macro_code; } double;
}
u2 defining_class;
u2 code_length;
u1 code[code_length];
} macro_table[macro_table_length];
}
MACRO_TYPE_SIMPLE = 0: A macro with a one-byte code
MACRO_TYPE_DOUBLE = 1: A macro with a two-byte code
マクロ定義は JVM に、全てのマクロ定義のコードを単独の配列に並べること
で、とても小さな形態で格納できる。新たなマクロを定義するための負担は 1 バ
イトと配列の目次の大きさにまで削減できる。実行システムのアーキテクチャー
に依存して、この配列の大きさは変わるかもしれない。各命令の先頭位置を示す
のに 2 バイト使うことで、配列の拡大は防げる。マクロ定義コードの長さを示す
新たなのフィールドを持つ代わりに、マクロ定義コードは終端に macro_end 命令
を加えるように実装した。2 バイト命令の後続バイトは、常に小さいものから使
われる。こうして、同じ先頭命令コード の 2 バイトマクロは全て、単独の配列に
格納できる。新しい命令コードはすでに利用できる領域が全て使われるまで 2 バ
イトマクロには割り当てあられない。
56
6.9
付録 B
後述のコードは標準的なバイトコード インタープリターの中核を示している。
インタープリターはメソッドが呼び出されるたびに呼び出される再帰的な関数と
して書かれている。従って関数の局所変数は、JVM における各メソッドのスタッ
クフレームと対応している。その次のソースは、インタープリターが単バイトの
マクロ命令の実行をサポートできるように修正されたものを示している。2 つの
小さなスタックがプログラムカウンターの流れと、クラスを定義する定数プール
を保持している。定数参照は、定義クラスで行われる。例外が発生するとスタッ
クは消去される。マクロ命令を実行するときは、その前のプログラムカウンター
と定義クラスがスタックに押し込まれ、新しい定義クラスが実行されるマクロか
ら取り込まれる。マクロの終了で、スタックからのプログラムカウンターと定義
クラスの抜き出しが行われる。
StackItem *interpretMethod( Method *m, StackItem *vars ) {
unsigned char c, d, type, *pc;
StackItem *sp, *vars;
/*...other local variables...*/
pc = m->code;
/*...other initializations...*/
while(1) {
c = *pc++;
switch(c) {
case ACONST_NULL: sp--; sp->r = NULL; break;
case ICONST_0: sp--; sp->i = 0;break;
case LDC1:
d = *pc++;
type = m->constant_pool[d].tag;
switch(type) {
case CONSTANT_Integer:
sp--; sp->i = m->constant_pool[d].value.c_int; break;
57
/*...other types...*/
}
break;
case ATHROW:
throwException( sp[0].r );
break;
/*...other instructions...*/
default:
VM_erroe( "unknown opcode %d", c);
break;
}
}
/*...release resources and return...*/
}
StackItem *interpretMethod( Method *m, StackItem *vars ) {
unsigned char c, d, type, *pc;
StackItem *sp, *vars;
/*...other local variables...*/
unsigned char *pc_stack[macroTable.max_nesting];
Class *cp, *cp_stack[macroTable.max_nesting];
int stack_index = 0;
pc = m->code;
/*...other initializations...*/
cp = m->class;
while(1) {
c = *pc++;
switch(c) {
case ACONST_NULL: sp--; sp->r = NULL; break;
case ICONST_0: sp--; sp->i = 0;break;
58
case LDC1:
d = *pc++;
type = cp->constant_pool[d].tag;
switch(type) {
case CONSTANT_Integer:
sp--; sp->i = cp->constant_pool[d].value.c_int; break;
/*...other types...*/
}
break;
case ATHROW:
stack_index = 0;
throwException( sp[0].r );
break;
/*...other instructions...*/
case MACRO_END:
stack_index--;
pc = pc_stack[stack_index];
cp = cp_stack[stack_index];
break;
default:
if( macroTable.table[c] == NULL ) VM_erroe( "unknown opcode %d", c);
pc_stack[stack_index] = pc;
cp_stack[stack_index] = cp;
stack_index++;
pc = macroTable.table[c]->code;
cp = macroTable.table[c]->defining_class;
break;
}
}
59
/*...release resources and return...*/
}
60
7.
7.1
比較検証
Cooper99
過去の研究者たちはプログラムの格納スペースの縮小に様々な方法を発展させ
てきた。1 つの方法はディスク上の実行プログラムに対してデータ圧縮を適用す
ることである。しかしこれはプログラムが実行されるためにメモリに読み込まれ
るときに解凍しなければならない。二次記憶の使用量を減らすだけでなくこの方
法はモバイルやネットワーク環境でプログラムを読み込む時間の短縮も実現して
いる。この方式の利点はコンパイラの支援を必要とせずどのような例にも適用で
きることである。
二次記憶の削減と違って、メモリ使用量の削減手法はデータとかスタックでな
くてコード の実行領域に注目してきた。多くのコンパイラ最適化手法が小さな
コードを生成するために発展してきた。こうした方法はコードサイズをハードの
支援や実行時間の大きな制約なしに縮小できるように設計されている。
多くの研究者が実行形式のプログラムそのものが何らかの形で圧縮されたまま
メモリ上に格納され実行時にある種の解凍段階を経る必要のある方法を実験して
きた。1 つの方法はデータをキャッシュサイズの塊に分けて圧縮し 、キャッシュミ
スヒットが生じるたびに解凍してキャッシュに展開すると言うものである。他に
も手続きごとに独立して圧縮し 、呼び出されるたびに解凍するというアプローチ
もある。3 つめの方法はコード 列の塊ごとにプログラム全体の辞書を作ってから
命令フェッチの段階で解凍するもので、与えられたプログラムの都合の良い符号
化を作ることに他ならない。
本研究ではソフトウェアのみの利用によるコード 圧縮を考えている。具体的に
はコード サイズを縮小するために尾部結合と手続き抽出という最適化を施すも
のである。この手法は Fraser らによって研究された方法を拡張したものである。
Fraser らの研究と同じくサフィックス木を使って繰り返しのコード 断片を同定し 、
実際の圧縮のためにはクロスジャンプと手続き抽出を適用する。しかし 、本研究
はいくつもの点で既存の研究とは異なる。まず RISC 命令セットに対するコード
圧縮の効果を評価した。Fraser らは VAX11/780 上で UNIX のユーティリティー
61
に対してテストをしたが平均圧縮率が 7%の一部の結果しか報告しなかった。また
コンピューターアーキテクチャーやコンパイラの最適化手法も VAX の時代とは
大きく変わっているので、この種のコード 領域最適化の効果を再評価する必要が
あった。次にコード圧縮と既存の最適化手法との相互作用を調査し、最適化がコー
ド 圧縮によって得られる結果に大きく影響することを示した。3 つ目は重要な拡
張として圧縮時のレジスタ名の違いを扱えるように改良した。最後に実行時のプ
ロファイル情報の注意深い利用がコード 圧縮でしばしばもたらされる実行速度の
低下を抑えられることが分かった。
7.2
Clausen98
コード 圧縮と言う考え方は全く新しいものではない。Fraser や Myers 、Vendit
はアセンブラコードを sux tree を使って圧縮する似たような方法について述べ
ている。この方法では平均7%という圧縮率を達成している。パラメータ化された
パターンを使って内部分岐を圧縮し 、合流するコード 列に関してはクロスジャン
プと言う手法を実装した。しかし 、この方法はコード 断片がスタックに影響を与
えないことが必要で、効果を制限してしまっている。
Ernst らは転送用にも実行用にコードを圧縮する方法 [4] について述べている。
この方法では実行コードに gzip を適用した場合と同等の圧縮率を達成している。
そのために特別なバイトコード 言語を開発し 、パターンを生成する為に末尾から
結合していく方法を使っている。この圧縮方法は、今回の方法よりもよい結果を
示してはいるが、かなりの RAM を必要とするので、一部の組み込み機器では利
用できない。
Proebsting は「超演算子」を使った C インタープリター [8] について述べてい
る。こうした演算子は、lcc が生成する樹状の中間表現から自動的に導き出され
る。それから演算子は特化した命令セットとそれを実行できるインタープリター
を生成するために使用される。この変換のねらいは実行速度の改善であるが、適
度なプログラムサイズの縮小も得られる。しかし 、生成されるインタープリター
のサイズ増加が問題である。特定のインタープリターを使うと言う方法も、組み
込みシステムにおいては考えられる。例えば 、一般的な実行環境に関して特化し
62
たインタープリターなどである。
Franz と Kistler は Java バイトコードに替えて SLIM バイナリー [3] というも
のを示した。SLIM バイナリーはかなり小さなプラットフォームフリーの構造化
プログラム表現で、必要時最適化コンパイラでバイナリーコードに翻訳されるよ
うに設計されている。構造化された表現と言うのは最適化に必要な情報を含める
ことが出来るので、コンパイル時の負荷と言うのはほとんど無視できるし 、生成
されるバイナリーコードは通常の最適化コンパイラで生成されたコードと同等の
効率を見せる。しかし 、SLIM バイナリーは圧縮された状態では逐次実行は簡単
ではなく、実行前にバイナリーコードにコンパイルしてやる必要がる。この点が
組み込みシステムには向かない点である。
7.3
Sutter
コード 圧縮には多くの研究がなされているが、その多くは保存領域や転送コス
トを減らすために、実行ファイルを出来るだけ小さくすることに着目している。
こうした方法は、比較的小さな圧縮表現が得られる事が多い。しかし 、引き換え
に実行前に元のサイズに解凍する必要があったり、圧縮されたまま直接実行する
ためには特別なハードウェアの支援を必要としたりする。特に解凍作業と言うの
はメモリが限られている組み込み機器などにおいては大きな障害となることもあ
る。一方で一切の解凍作業や、特別なハード ウェアの支援を必要としないプログ
ラムの圧縮方法も研究されている。
これまでの小さな実行コードを生成するための研究の大半は、実行プログラム
を単なる命令の線形列として扱っている。そこで sux tree を利用してプログラ
ム中に繰り返される命令を同定し 、それを抜き出して関数にすることになる。こ
うした研究はどれも、プログラム中のデータ領域の縮小には注意を払っていない。
こうした報告で得られる圧縮率は控えめで、平均して 4-7%である。最近こうした
方法とは逆に、プログラムを通常の制御フローグラフ表現で表して、コード 削減
を目的とする手続き間の最適化手法を積極的に使うことで、コードサイズにおい
て平均30%前後と言うかなりの縮小に成功した。しかし 、この研究は不要データ
の除去と、それが不要コードの削除に与える補助作用は考慮に入れていない。今
63
回得られた結果は前回のものに比べて、プログラム全体で5-6%の縮小が得られた
が 、その主な要因は不要データの除去によるものである。
プログラムからの未使用データの削除は、Srivastava と Wall や、Sweeney と
Tip が研究している。Srivastava と Wall は、リンク時の最適化手法 [10] につい
て述べている。これは Alpha で実行可能なコードをサブルーチン呼び出しに改善
するもので、実行ファイル中のグローバルアドレス表の大部分を削除できた。し
かし 、彼らの研究の目標はまず実行速度を改善することで、グローバルアドレス
表以外のデータ領域の削除に関しては調査されていない。Sweeney と Tip の研究
[13] は C++プログラム中の不要なデータメンバーの削除に限られた話で、オブ
ジェクト指向でない言語には適用できない。一方今回の方法は実行プログラムに
適用するので、あらゆる言語で書かれたプログラムに応用可能である。またこれ
らの研究は、不要データの削除と不要コードの削除の間に密接な関係があること
に注目していない。Sweeney の報告では平均4.4%の縮小しか得られていないが、
今回の研究ではコードとデータの両方の削除を考慮することで、全体で 27-32%の
縮小が得られた。
7.4
Nystr
om
コード 圧縮アルゴリズムは大抵機械語に適用され、命令列の繰り返される出現
を文字列マッチングの技術を利用して特定する。
最近 Cooper と McIntosh はもっと複雑なコード 圧縮法 [2] を提唱した。彼らも
文字列マッチングの技術に頼ってはいるが、レジスタ名を前回その名前が使用さ
れた場所への相対参照に改め、要約した表現を使うことでアルゴ リズムの適用範
囲を拡大している。こうすることで、レジスタの利用だけが異なっていた二つの
プログラム断片を同一の表現と見なせるようにした。Debray,Evans,Muth は実行
コードからフローグラフを生成し 、マッチングの技術を利用してフローグラフの
断片が繰り返し出現しているのを発見した。[9] このアルゴ リズムは異なるレジ
スタを利用しているコード 断片を同一視でき、未使用なレジスタが充分にある環
境では、こうした断片を同じサブルーチンに置き換えられるようにレジスタを割
り当てなおす。
64
Zastre は機械語レベルでの手続き抽出を考え、パラメータを使った手続きの抽
出方法 [15] を提唱している。Vahid は VHDL の類似領域を特定して、手続き呼び
出しに置き換えることのできる変換ツール [14] について述べているが、このツー
ルはそれぞれの領域が同じ意味であることは保証していず、どちらかというと領
域が安全に呼び出しに置換できるかはユーザーの決定に頼っている。
多くの研究者が、特殊なハードウェアに頼るか、組み込みシステムの設計に何
か要求されるコード 圧縮技術を提唱している。Ernst らはコードが メモリに読み
込まれるときに解凍される圧縮方法について述べている。これはもちろん、プロ
グラムはネットワークを通じてダウンロードできるか、ハード ウェア上に複数の
メモリ領域がある必要がある。1 つは（多分ディスクで）通常プログラムが格納
されていて、また 1 つはプログラムが実行前に読み込まれる領域である。他の圧
縮方法としては、専用のハード ウェアがコードが命令キャッシュに読み込まれる
ときに解凍するのを仮定している。Liao らは文字列マッチングを使った圧縮方法
を、特殊な命令を拡張したプロセッサ [12] で改良できることを示した。特殊な命
令と言うのは任意の命令列をサブルーチンのように扱えるものである。こうした
方法は既存のプロセッサで実行可能なコードを生成する方法よりよい結果を示す
ことが多いが、こうした利点は解凍に必要な機構の手間や不都合と比較する必要
がある。
多くの既存のコンパイラ最適化手法は、コード量を減らせるかもしれない。Liao
らは、小さな目的コードを生成するための命令選択をするアルゴ リズム [11] につ
いて調査した。Cooper らは 、与えられたソースプログラム毎に、最も小さな目
的コードを生成するように最適化段階の順序を決定するのに遺伝的アルゴ リズム
[5] を用いた。
65
8.
まとめ
今後、特に組み込み機器分野などコード サイズが重要になる分野でコンピュー
ターの使用が増えると考えられる。こうした中でコード 圧縮技術というのは大き
な意味を持つ。そこでこうした技術について幅広い調査を試みた。
ここに示してきたように、コードサイズを縮小する研究そのものはかなり以前
から行われていて、基幹となる技術はパターンマッチングを利用した重複部分の
探索と、その結果を特別な処理を必要とせずに実行できる状態で圧縮する技術と
なる。もちろん特別なハードウェアのサポートなどを前提とした圧縮技術も研究
されているし 、こうした手法は一般に高い圧縮率を示すが、コストやサイズの削
減を目指す組み込み分野にはあまり向いていない。ネットワーク経由でプログラ
ムの配信を行う場合などで、ユーザー側の端末に充分な資源が見込める場合はこ
うした手法も利用できると考えられる。
様々な抽象化などを利用して重複部分の拡大を図る方法や、特別な命令セット
を用意して圧縮率の向上を図るような、既存の研究の拡張を試みるアプローチが
多数行われている。近年ではこれに加えて、組み込み、モバイル環境を意識した、
リアルタイム性を損なわないように実行速度の低下を招かない圧縮方法の研究が
盛んになってきている。
66
謝辞
最後になりますが、本研究を進めるに当たって幾度も適切な指導を下さった福
田晃教授に深く感謝の意を示すものであります。また、本研究について適切な助
言を頂いた渡邉勝正教授に深謝致します。さらに調査にあたって様々な助力を頂い
た中西恒夫助手に深謝いたします。同時に公私にわたり研究活動を支えて下さっ
た福田研究室の皆様にも同様の感謝を表すものであります。
67
参考文献
[1] Eugene W. Myers Christopher W. Fraser and Alan L. Wendt. Analyzing and
compressing assembly code. Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction SIGPLAN Notices, 19(6):117{121, June
1984.
[2] Keith D. Cooper and Nathaniel McIntosh. Enhanced code compression for
embedded risc processors. Proceedings of the ACM SIGPLAN '99 Conference on Programming Languages Design and Implementation SIGPLAN No-
, 34(5):139{149, May 1999.
tices
[3] Michael Franz and Thomas Kistler. Slim binaries.
40(12):87{94, December 1997.
,
Communication on ACM
[4] Christopher W. Fraser Steven Lucco Jens Ernst, William Evans and Todd A
Proebsting. Code compression. Proceedings of the ACM SIGPLAN'97 Conference on Programming Languages Design and Implementation, 32(5):358{
365, June 1997. ACM SIGPLAN Notices.
[5] Philip J. Schielke Keith D. Cooper and Devika Subramanian. Optimizing
for reduced code space using genetic algorithms. LCTES 99, June 1999.
[6] Charles Consel Lars Raeder Clausen, Ulrik Pagh Schultz and Gilles Muller.
Java bytecode compression for embedded systems. Irisa, technical report 1213
edition, December 1998.
[7] E. M. McCreight. A space-economical sux tree construction algorithm.
Journal of ACM, 23(2):262{272, April 1976.
[8] Todd A. Proebsting. Optimizing an ansi c interpreter with superoperators.
Proceedings of the 22nd Annual ACM Symposium on Principles of Progamming Languages
, pages 322{332, January 1995.
68
[9] William Evans Saumya Debray and Robert Muth. Compiler Techniques for
Code Compression. University of Arizona, 97 edition, April 1999.
[10] A. Srivastava and W. Wall. Link-time optimization of address calculation
on a 64-bit architecture. Proceedings of the Programming Languages Design
and Implementation, pages 49{60, June 1994.
[11] Kurt Keutzer Steve Tjiang Stan Liao, Srinivas Devadas and Albert Wang.
Instruction selection using binate covering for code size optimization. Proceedings of the International Conference on Computer-Aided Design, pages
393{399, 1995.
[12] Srinivas Devadas Stan Liao and Kurt Keutzer. Code density optimizations
for embedded dsp processors using data compression techniques. Proceedings
of the 15th Conference on Advanced Research in VLSI, March 1995.
[13] P. F. Sweeney and F. Tip. A study of dead data members in c++ applications. Proceedings of the Programming Languages Design and Implementation, pages 324{333, June 1998.
[14] Frank Vahid. Procedure exlining: A transformation for improved system and
behavioral synthesis. International Symposium on System Synthesis, pages
84{89, September 1995.
[15] Michael Joseph Zastre. Compacting object code via parameterized procedural abstraction, 1995.
69
付録
A.
内容梗概
A.1
Fraser84
本研究では一般的なデータ圧縮アルゴリズムのアセンブラコードへの適用につ
いて説明する。システムの対象は限定せず、クロスジャンプと手続きの抽出を一
般化する。システムは実行時間とメモリ空間を交換する空間の最適化に利用でき、
アセンブラコードを逐次実行できるコードに変換し 、実システムでも仮想システ
ムでも標準的なデザインを自動定式化する支援をする。
A.2
Cooper99
本研究では実行プログラムを読み込んで実行するのに必要なメモリを減らすコ
ンパイラ手法について調査する。組み込みシステムにおいてはコストの観点から
ROM 及び RAM のサイズを減らすことに強い関心が置かれていて、コンパイル
済みのコードサイズはますます重要になっている。同時にモバイルそしてネット
ワークコンピューティングにおいても、実行前にコードを転送する必要からコー
ド サイズには大きな関心が寄せられている。本手法はパターンマッチングの手法
を用いて、繰り返される命令プログラムのコード 領域を縮小することに焦点を置
いている。他の手法と違ってこのアプローチでは、プログラムは解凍段階を経な
いで直接実行可能なままに保たれている。本手法は industrial-strength optimizing
コンパイラに組み込んだ。本コンパイラはコード 圧縮と他の最適化との相互作用
を調査するのに向いており、また事前に最適化されたコードに対しては圧縮が難
しいと言う都合があったからである。本章の主眼は、RISC アーキテクチャーに
対するコード 圧縮の総括的な実験評価、反復コード 断片をよりよく同定するため
のより強力なパターンマッチング手法と圧縮による速度低下を低減するためのプ
ロファイルによるコード 圧縮形態を含めたものである。
70
A.3
Clausen99
組み込みシステムとか似たような環境で動作するプログラムはメモリ量の制限
と時間制約を受ける。共通命令列の要素化が Java のプログラムにど う自動的に適
用されるかを示す。一連の実験に基づいて、実行時間の制約を30%以内に抑えなが
ら平均30%のプログラムサイズの縮小ができることを説明する。本論文のコード
実行時に必要な標準 Java インタプリタへの変更が Harissa 仮想機械で Java コー
ド の要素化アルゴ リズムとともに実現されている。
A.4
Runeson00
メモリサイズは、組み込みシステムの開発においてよく重要な経済性を決める
要素となるので、生成される実行コードのサイズを削るためのコンパイラ最適化
手法を探すことが望まれている。こうしたコード 圧縮方法の 1 つが手続き抽出で
ある。それは、等価なコード 断片が繰り返し出現するときに、これらを新たなサ
ブルーチンにまとめると言うものである。本研究では、手続き抽出を中間コード
の段階で適用する有効性について調査する。過去の機械語段階に対する研究では、
レジスタの配置と割り当て時の特質による複雑さを処理する必要があった。レジ
スタ配置前に手続き抽出を適用することでこの問題を避け、またレジスタ配置に
関する強力な最適化手法の恩恵も引き出すことが出来た。実験結果は、中間コー
ド のサイズにおいてかなりの縮小を示した。
A.5
O'Sullivan94
Glasgow Haskell Compiler による実行プログラムの動作は高速であるが、Chalmers'
Haskell B compiler によって生成されるプログラムに比べてかなり大きくなる。
本研究では、不要に繰り返される情報について Fraser らが示している方法につい
て論じる。この簡単な解析によって本例で得られた結果は、実行時の記憶システ
ムが最適化の第一候補であるということである。ここでは、塊単位で保持される
記憶管理表の共通の情報を、共有の表に合体させることで塊単位の表で消費され
る空間の総量を減らし 、このシステムに合わせてガーベッジコレクションアルゴ
71
リズムを変更した。こうした修正の結果、修正済みのコンパイラが生成するプロ
グラムはバイナリー状態で、平均13%通常のコンパイラによるものよりも小さく
なり、実行時に生じる性能低下はおおよそ1%であった。
A.6
Zastre
本研究では、パラメータを利用した手続き抽出に関して調査した。これはコー
ド サイズの縮小だけを目的とした、手続き抽出と言う最適化手法の拡張である。
これまでに発表されている手続き抽出の実装と言うのは、命令列が厳密に一致し
ている場合に限って領域が節約できた。ここでは、次のような場合常に圧縮によ
る領域の節約が可能であることを示す。1. 全てのパターンがいずれかの手続きに
含まれていて、2. 各手続きに含まれるパターンの実体を慎重に選択した場合。こ
のアルゴリズムはパラメータ化しない手続きを使うことに限った方法に比べてか
なりの節約に成功した。
A.7
Debray99
近年コンピューターと、使えるメモリ量に制限のある様々な機器とを組み合わ
せることに注目が集まっている。こうした流れの中では、出来る限りアプリケー
ションのサイズを小さくする試みが望まれる。本研究は、小さな実行コードを生
成する圧縮を達成するために、コンパイラ技術の利用を試みる。研究の中核は、
どのようにして等価なコード 断片を見つけ、sux tree に基づく手法にみられる
ようにコード 列を線形に扱う方法だけに頼らずに、まとめられるかを示すことで
ある。どのようなコード 断片が等価であるかをもっと柔軟に判断できるコード 圧
縮の枠組みを提供する。本手法は、過去の方法よりも大きな圧縮を実現できるバ
イナリー書き換えツールとして実装した。
A.8
Srivastava94
64 ビットアドレスを処理する新しいアーキテクチャーのコンパイラは、実行時
に大量のメモリを必要とするコードを生成する。手続きやグローバル変数は、グ
72
ローバルアドレス表を参照して間接アクセスされ、呼び出して続きは適切な表へ
のアドレス計算を確立する為のコードを含む。大量のメモリを必要としない多く
のプログラムの場合は、これはプログラムのサイズや実行時間の減少に応じて比
較的簡単な処理で済む。
リンク時のコード 修正システム OM で、Alpha の AXP 上でグローバルアドレ
スの使用に関した変換を行った。単純ではあってもこうした変換はプログラム全
体に関する最適化なので、プログラム全体を一度に確認できるときにしか実行で
きない。従ってリンク時というのは理想的な最適化のタイミングとなる。
実行した最適化の詳細と、プログラムのサイズと性能に及ぼした影響について
説明する。比較的控えめな、コードの移動を伴なわない変換は SPEC ベンチマー
クに対して平均1.5%の高速化を達成した。もっと積極的な、リンク時にはそれほ
ど 困難ではないが綿密にプログラムの構造を理解する必要のある変換は、さらに
よい結果を示した。プログラムのサイズに関しては10%以上、性能は平均で 3.8%の
改善が見られた。
手続き間の最適化を含めた包括的にコンパイルされるプログラムにおいてさえ、
この手法で静的にリンクされる未コンパイルのライブラリコードがある場合先の
値に近い結果が出た。ベンチマークのソースをこの方法でコンパイルしたときも、
控えめな変換で平均1.35% 、積極的な変換では3.4%の改善を達成した。
A.9
Lekatsas98
近年の組み込みシステムの多くでは、メモリというのは最も制限されやすい資
源の 1 つである。コード 圧縮はかなりの領域節約を達成できる。圧縮コード CPU
においては 、キャッシュミスヒットをきっかけに メインメモリブロックがキャッ
シュに転送される前に解凍される。コードはどこからでも（少なくともキャッシュ
領域の境界部では）解凍できるので、大半のファイル指向の圧縮方法は使えない。
ここで領域を節約できて、簡単に解凍できるようにコードを圧縮する 2 つのアル
ゴ リズムを提案する。1 つは命令セットに独立であり、1 つは命令セットに依存し
ている。典型的な RISC（ MIPS ）と CISC（ x86 ）命令セットに関して実験して、
既存のファイル指向の圧縮方法と比較する。
73
A.10
Proebsting95
バイトコード インタープリターの最適化に超演算子を導入する。超演算子はよ
り小さな演算子を自動的に結合した仮想機械の演算子で、演算前の負荷を避ける
ことが出来る。超演算子は実行ファイルのサイズを縮小し 、インタープリター上
のプログラムの実行速度を 2 倍にも 3 倍にもする。本研究では、単純な演算子の
使用パターンから強力な超演算子を導く発見的な手法を説明する。
超演算子を採用した翻訳機構とインタープリターの設計と実装について述べる。
（自動生成されるものでも手動で選択されるものでも）超演算子の仕様から、シス
テムはアセンブラ言語で仮想機械を有効に実装する。システムは可搬性に富み、
現在は MIPS R3000 と SPARC の上で動いている。
A.11
Vahid95
手続きインライン展開の逆問題の解法として、宣言の連なりを手続き呼び出し
で置換する方法を示す。2 つの手法が考えられる。1 つは冗長な宣言の連なりを
探して、1 つの手続きへの呼び出しに置換するもので、もう 1 つは大きな宣言集
合をいくつかの、それぞれが異なる計算を行う手続きに分解するものである。こ
の手続きの外部移動は読みやすさを重視して記述された動作仕様を、手続きは統
合ツールの結果を大幅に改善するので効率よく実装する。この手法の有効性をい
くつかの例で示す。
A.12
Liao95'
組み込み DSP プロセッサ向けのコード 生成時に生じる命令選択問題に注目す
る。こうしたプロセッサはかなり特殊なデータパスをもち、既存のコード 生成法
では大抵効率の悪い結果となる。
命令選択は有効非巡回グラフ（以下 DAG ）の包含に定式化される。従来の命
令選択の手法は発見的で、DAG を木に分解して、それぞれ独立に計算していた。
この分解は元の DAG の局所最適解は与える。一方 DAG 包含問題は、2 分木包含
問題として定式化され、分岐と境界法で発見的にあるいは厳密に解かれる。
74
累算機に基づくアーキテクチャーでは、DAG での最適な命令選択は DAG の
ノード の部分スケジューリングが必要であることを示し 、2 分木包含問題を取り
こぼしや再読み込みを最小にするように拡張する。また典型的な DSP の特殊な
データの転送コストが 2 分木包含問題にモデル化できるかを示す。
A.13
Lefurgy98
組み込みマイクロプロセッサは非常にコスト、電力、大きさの制約が厳しい。
最も一般的な制御指向の組み込み応用例では、回路のかなりの部分が命令メモリ
に使われる。集積回路の価格はダ イサイズと強く関わっていて、メモリサイズは
ダ イサイズに比例するので、小さなプログラムと言うのは、小さく安価なダイを
組み込みシステムに利用できることになる。プログラムメモリに関するさらなる
要求として、比較的最近の組み込みシステムへの高級言語の利用と言うこともあ
る。典型的なコードサイズの増加と共に、高級言語が開発コストを抑えるために
使われるようになっている。しかし 、こうした言語のコンパイラと言うのは大抵、
職人芸で最適化されたアセンブラコードに比べてかなり大きなコードを生成する。
そのため、プログラムを小さな表現にコンパイルすることは、ソフトウェアの開
発コストも製造コストも抑えるために重要なのである。
高性能システムも、命令キャッシュミスによる遅延のためにプログラムサイズ
の影響を受ける。Digital 社で DEC21064Alpha 上の SQL サーバーの性能を計る
研究が行われた。命令キャッシュミスのために、プログラムはプロセッサが提供
してる倍の命令幅を必要としてしまった。これは、プロセッサのサイクルタイム
と標準 DRAM のアクセスタイムの差が増えていくに連れて悪化していく。プロ
グラムの縮小は命令キャッシュミスを減らす方法の 1 つで命令幅を広げる。
A.14
Zastre95
現在のコンパイラの最適化に関する研究はコードのスピードを上げる変換に集
中している。オブジェクトファイルのサイズを減らすことも、コードが少なけれ
ば早く実行できるということで目的になることもある。本研究ではパラメータ化
した手続き抽出について調査する。これはコード サイズを減らすことのみを目的
75
とした最適化の拡張である。これまでに発表されている手続き抽出と言うのは命
令列が厳密に一致する場合には領域が節約できると言うものである。
（つまりコー
ド 列間で、命令の操作部とオペランド 部が同じ ）研究者達は、差異をパラメータ
とするのはコストがかかりすぎると感じてきた。しかし 、思い切って曖昧さを含
めたマッチングによる領域節約の可能性は調べられていない。ここで次の場合に
常に領域節約（圧縮）が実現できることを示す。1. パターンが複数の手続きでカ
バーされていて、2. どのパターンがどの手続きにカバーされているかを慎重に選
んだ場合である。発見的なアルゴ リズムで、パラメータ化した手続きとそうでな
いものを混ぜて選ぶことで、パラメータ化されない手続きだけを利用するのと比
較してかなり多くの領域節約が達成できる。
A.15
Sutter
段々多くの計算機が、利用できるメモリ総量に制限のある機器と組み合わせら
れるようになっている。結果として、プログラムサイズの自動的な縮小に研究の
焦点が移っている。この分野の文献は、全てではないにしても大半はコード 圧縮か
不要データの削除に焦点を当てている。しかし 、これはコードアドレスとはデー
タに他ならず密接に関連している。本研究の主題はコードとデータ圧縮の組み合
わせが、どのようにコードとデータのアドレスを利用してリンク時のコード 圧縮
システムによって達成されるかを示すことである。提案する解析法はリンクされ
たコード の基本属性から作られ、一般的に応用できる。コードとデータの圧縮の
組み合わせは SPEC2000 と MediaBench プログラム上で評価され、バイナリープ
ログラムサイズで24.0%-45.8%の縮小を達成した。この圧縮では速度低下は招か
れず、結果的に圧縮されたプログラムは平均で5%程高速化した。
A.16
Nystr
om
組み込みシステムにおいて、メモリは高価で時には限られた資源である。組み
込みシステム用コンパイラの開発過程で、生成されるコードのサイズを縮小する
最適化手法（コード 圧縮）を見つけることが望まれる。こうした方法の一つが手
続き抽出である。それは等価なコード 断片の繰り返される出現を新たなサブルー
76
チンにまとめ上げることである。通常この方法は機械語段階で適用される。本研
究では手続き抽出を中間言語の段階で適用する見込みを調べた。コード 圧縮段階
がレジスタ割り当てや多くの最適化段階の前に行われるので、似たような中間言
語表現が例えばレジスタ割り当ての影響で、異なる機械語に割り当てられて圧縮
の機会が失われることは避けられる。
77