文献の略記法
CC'nn: Proceedings of International Conference of Compiler Construction held in 19nn
Compiler'nn: Proceedings of the ACM SIGPLAN'nn Symposium on Compiler Construction
PLDI'nn: Proceedings of the ACM SIGPLAN'nn Conference on Programming Language Design and Implementation
TOPLAS: ACM Transactions on Programming Languages and Systems
CACM: Communications of the ACM
n-th PPoPP: Proceedings of the n-th ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
n-th POPL: Conference Record of the n-th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
ASPLOS: Architectural Support for Programming Languages and Operating Systems
LNCS: Lecture Notes in Cmputer Science, Springer-Verlag
ICS'xx: Conference Proceedings, 19xx International Conference of Supercomputing
PACT'nn: Proceedings 19nn International Conference on Parallel Architecture and Compilation Techniques
MICRO nn: Proceedings of the nn-th IEEE/ACM International Symposium on Microarchitecture
第１部 コンパイラの概要
1．はじめに
１．１ コンパイラとは
１．２ 変換系と通訳系
２．コンパイラの簡単な例
２．１ 後置記法
２．２ スタック
２．３ 簡単なコンパイラの例
２．４ コンパイラの論理的構造
２．５ コンパイラの物理的構造
第２部 コンパイラの構成
３．文法と言語
３．１ バッカス記法
[Naur60] Naur, P. et al.:
Report on the algorithmic language ALGOL 60,
CACM, vol.3, no.5, pp.299-314, 1960.
３．２ 構文図式
３．３ 文法と言語の形式的定義
３．４ 解析木
３．５ あいまいな文法
４．字句解析
４．１ 文字読取￥り
４．２ 字句読取り
[Gagn98] Gagnon, E.:
SableCC, An Object-Oriented Compiler Framework,
Master thesis, School of Computer Science, McGill University, 1998.
４．３ 正規表現と有限オートマトン
４．３．１ 正規表現
４．３．２ 正規表現から非決定性有限オートマトンへ
４．３．３ 非決定性有限オートマトンから決定性有限オートマトンへ
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
４．３．４ 有限オートマトンの状態数の最小化
４．３．５ 字句解析器生成系
[Lesk2-75] Lesk, M.E. and Schmidt, E.:
Lex - A Lexical Analyzer Generator,
Comp. Sci. Tech. Rep. 39, Bell Laboratories, 1975.
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
[Levi3-90] Levine, J.R., Mason, T. and Brown, D.:
lex & yacc,
O'Reilly & Associates, 2nd edition, 1990.
村上列訳：lex & yacc プログラミング，アスキー出版局、1995.
[Gros89] Grosch, J.:
Efficient Generation of Lexical Analysers,
Software -- Practice and Experience, vol.19, no.11, pp.1089-1103, 1989.
[Gray5-92] Gray, R.W., Heurig, V., Levi, S.P., Sloane, A.M., and Waite, W.M.:
Eli: A Complete, Flexible Compiler Construction System,
CACM, vol.35, no.2, pp.121-131, 1992.
[Bumb2-93] Bumbulis, P. and Cowan, D.D.:
RE2C: A More Versatile Scanner Generator,
ACM Letters on Programming Languages and Systems, vol.2, no.1-4, pp.70-84, 1993.
[Wait86] Waite, W.M.:
The Cost of Lexical Analysis,
Software -- Practice and Experience, vol.16, no.5, pp.473-488, 1986.
[Brou3-98] Brouwer, K., Gellerich, W. and Ploedereder, E.:
Myths and Facts about the Efficient Implementation of Finite Automata and Lexical Analysis,
CC'98 (LNCS 1383), pp.1-15, 1998.
４．４ 字句読取りプログラムの例
４．４．１ 浮動小数点定数の読取り
[JIS93] JIS X 3010-1993 プログラム言語C,
ISO 9899(Information technology--Programming languages-C)をJIS化したもの
[中田2-86] 中田育男、佐々政孝：
意味規則付き正規表現とデータ構造直結型プログラムへの応用、
コンピュータソフトウェア、３巻１号、pp.47-56、1986.
４．４．２ コメントの読取り
[中田93] 中田育男：
拡張正規表現によるパターンマッチングアルゴリズムの生成、
コンピュータソフトウェア、１０巻１号、pp.63-67、1993
４．４．３ 最長一致と最短一致
[Reps98] Reps, T.:
"Maximal-Munch" Tokenization in Linear Time,
TOPLAS, vol.20, no.2, pp.259-273, 1998.
[Clar2-97] Clarke, C. L. A. and Cormack, G. V.:
On the Use of Regular Expressions for Searching Text,
TOPLAS, vol.19, no.3, pp.413-426, 1997.
５．構文解析
５．１ 構文解析手法の簡単な歴史
[Same2-60] Samelson, K. and Bauer, F.L.:
Sequential Formula Translation,
CACM, vol.3, no.2, pp.76-83, 1960.
[Floy63] Floyd, R.W.:
Syntactic Analysis and Operator Precedence,
J. ACM, vol.10, no.7, pp.316-333, 1963.
[Knut65] Knuth, D.E.:
On the Translation of Languages from Left to Right,
Information and Control, vol.8, nol.6, pp.607-639, 1965.
[DeRe71]DeRemer, F.L.:
Simple LR(k) Grammars,
CACM, vol.14, no.7, pp.453-460, 1971.
[John75] Johnson, S.C.:
Yacc--Yet Another Compiler Compiler,
Comp. Sci. Tech. Rep. 32, Bell Laboratories, 1975.
[Conw63] Conway, M.E.:
Design of a Separable Transition-Diagram Compiler,
CACM, vol.6, no.7, pp.396-408, 1963.
[Lewi2-68] Lewis, P.M. II and Stearns, R.E.:
Syntax-Directed Transductions,
J. ACM, vol.15, no.7, pp.465-488, 1968.
[Lewi3-76] Lewis, P.M. II, Rosenkrantz, D.J. and Stearns, R.E.:
Compiler Design Theory,
Addison Wesley, 1976.
[Jens2-78] Jensen, K. and Wirth, N.:
Pascal User Manual and Report, 2nd edition,
Springer-Verlag, 1978.
[Wirt71] Wirth, N.:
The Design of a PASCAL Compiler,
Software--Practice and Experience, vol.1, pp.309-333, 1971.
５．２ 下向き構文解析法
５．２．１ 下向き構文解析法とその問題点
[Aho2-77] Aho, A.V. and Ullman, J.D.:
Principles of Compiler Design,
Addison Wesley, 1977.
土居範久他訳：コンパイラ，培風館，1986．
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
５．２．２ LL(1)文法
５．２．３ 再帰的下向き構文解析プログラム
５．２．４ 文法から再帰的下向き構文解析プログラムへ
[Jens2-78] Jensen, K. and Wirth, N.:
Pascal User Manual and Report, 2nd edition,
Springer-Verlag, 1978.
５．２．５ 非再帰的下向き構文解析法
５．２．６ あいまいな文法の扱い
[中田2-93] 中田育男，山下義行：
再帰的下向き構文解析における演算子順位構文解析、
情報処理学会論文誌、３４巻２号、pp.239-245、1993.
[Milt3-79] Milton, D.R., Kirchhoff, L.W., and Rowland, B.R.:
An ALL(1) Compiler Generator,
Compiler'79, pp.152-157, 1979.
[Parr2-94] Parr, T.J. and Quong, R.W.:
Adding Semantic and Syntactic Predicates to LL(k): pred-LL(k),
CC'94 (LNCS 786),pp.263-277, 1994.
５．３ LR構文解析法
[Knut65] Knuth, D.E.:
On the Translation of Languages from Left to Right,
Information and Control, vol.8, nol.6, pp.607-639, 1965.
[DeRe69]DeRemer, F.L.:
Practical Translation for LR(k) Languages,
Ph.D. thesis, MIT, Cambridge, Mass., Sept. 1969.
[DeRe71]DeRemer, F.L.:
Simple LR(k) Grammars,
CACM, vol.14, no.7, pp.453-460, 1971.
[小島3-74] 小島富彦、加藤正道、中田育男：
LR(k) Parser生成システムとそのFORTRANコンパイラへの応用、
情報処理、１５巻２号、93-100頁、1974.
[John75] Johnson, S.C.:
Yacc--Yet Another Compiler Compiler,
Comp. Sci. Tech. Rep. 32, Bell Laboratories, 1975.
５．３．１ 上向き構文解析法
５．３．２ LR構文解析の概略
５．３．３ SLR(1)構文解析
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
５．３．４ LR(1)構文解析
[Barr2-79] Barrett, W. A. and Conch, J.D.:
Compiler Construction: Theory and Practice,
Science Research Associates, 1979.
５．３．５ LALR(1)構文解析
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
[Kris2-81] Kristensen, B.B. and Madsen, O.L.:
Methods for Computing LALR(k) Lookahead,
TOPLAS, vol.3, no.1, pp.60-82, 1981.
５．３．６ あいまいな文法の扱い
５．３．７ 正規右辺文法のLR構文解析
[Naka2-86] Nakata, I. and Sassa, S.:
Generation of Efficient LALR Parsers for Regular Right Part Grammars,
Acta Informatica, vol.23, pp.149-162, 1986.
[佐々2-86] 佐々政孝、中田育男：
正規右辺文法のLRパーサの簡単な実現法、
情報処理学会論文誌、２７巻１号、pp.124-127、1986.
[張3-87] 張又普、中田育男、佐々政孝：
正規右辺文法の効率の良いLRパーサの簡単な実現法、
情報処理学会論文誌、２８巻１１号、162-167頁、1987.
[Zhan2-91] Zhang, Y. and Nakata, I.:
Generation of Path Directed LALR(k) Parsers for Regular Right Part Grammars,
Journal of Information Processing, vol.14, pp.325-334, 1991.
[森本98] 森本真一：
正規右辺文法のLALRパーサの新しい実現法、
情報処理学会論文誌、３９巻３号、684-691頁、1998.
５．４ 演算子順位構文解析法
５．４．１ 演算子順位文法
５．４．２ 演算子順位行列による構文解析
５．４．３ 演算子順位関数
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
５．５ 構文解析法の選択
[DeRe69]DeRemer, F.L.:
Practical Translation for LR(k) Languages,
Ph.D. thesis, MIT, Cambridge, Mass., Sept. 1969.
[小島3-74] 小島富彦、加藤正道、中田育男：
LR(k) Parser生成システムとそのFORTRANコンパイラへの応用、
情報処理、１５巻２号、93-100頁、1974.
[Gosl3-96] Gosling, J., Joy, B. and Steele, G.L., Jr.:
The Java Language Specification,
Addison Wesley, 1996.
[Sass4-80] Sassa, M., Tokuda, J., Shinogi, T. and Inoue, K.:
Design and Implementation of a Multipass-Compiler Generator,
Journal of Information Processing, vol.3, no.2, pp.77-86, 1980.
[Wirt71] Wirth, N.:
The Design of a PASCAL Compiler,
Software--Practice and Experience, vol.1, pp.309-333, 1971.
５．６ 構文解析器生成系
[John75] Johnson, S.C.:
Yacc--Yet Another Compiler Compiler,
Comp. Sci. Tech. Rep. 32, Bell Laboratories, 1975.
[Levi3-90] Levine, J.R., Mason, T. and Brown, D.:
lex & yacc,
O'Reilly & Associates, 2nd edition, 1990.
村上列訳：lex & yacc プログラミング，アスキー出版局、1995.
[Gros90] Grosch, J.:
Lalr - a generator for efficient parsers,
Software -- Practice and Experience, vol.20, no.11, pp.1115-1135, 1990.
[Penn86] Pennello, T.J.:
Very fast LR parsing,
Compiler'86 (SIGPLAN Notices vol.21, no.7, pp.145-151, 1986.
[Hors2-90] Horsepool, R.N., Whitney, M.:
Even faster LR parsing,
Software -- Practice and Experience, vol.20, no.6, pp.515-535, 1990.
[Donn2-91] Donnelly, C. and Stallman, R.:
Bison Reference Manual,
1991.
[wwwCUP] http://www.cs.princeton.edu/~appel/modern/java/CUP/
[Appe98] Appel, A.W.:
Modern Compiler Implementation in Java,
Cambridge University Press, 1998.
[Gagn98] Gagnon, E.:
SableCC, An Object-Oriented Compiler Framework,
Master thesis, School of Computer Science, McGill University, 1998.
[wwwSab] http://www.sable.mcgill.ca/sablecc/
[wwwJLe] http://www.cs.princeton.edu/~appel/modern/java/JLex/
[佐々3-93] 佐々政孝，石塚浩志，中田育男:
1パス型属性文法に基づくコンパイラ生成系Rie,
コンピュータソフトウェア, 10巻3号, 20-36頁, 1993年5月.
[wwwRie] http://www.is.titech.ac.jp/labs/saslab/Rie/rierelease.html
[Gray5-92] Gray, R.W., Heurig, V., Levi, S.P., Sloane, A.M., and Waite, W.M.:
Eli: A Complete, Flexible Compiler Construction System,
CACM, vol.35, no.2, pp.121-131, 1992.
[wwwEli] http://www.cs.colorado.edu/~eliuser/
[Moss90] Mossenbock, H.:
Coco/R -- A Generator for Fast Compiler Front-Ends,
Report 127, Institute fur Computersysteme, ETH Zurich, 1990.
[wwwCoc] http://cs.ru.ac.za/homes/cspt/cocor.htm
[Parr2-94] Parr, T.J. and Quong, R.W.:
Adding Semantic and Syntactic Predicates to LL(k): pred-LL(k),
CC'94 (LNCS 786),pp.263-277, 1994.
[Parr2-95] Parr, T.J. and Quong, R.W.:
ANTLR: A Predicated-LL(k) Parser Generator,
Software -- Practice and Experience, vol.25, no.7, pp.789-810, 1995.
[wwwANT] http://www.antlr.org/
[wwwJav] http://www.suntest.com/JavaCC/
[wwwCat] http://www.first.gmd.de/cogent/catalog/
６．意味解析
６．１ 意味解析とは
６．２ 記号表
６．２．１ 記号表の情報
６．２．２ 記号表の探索
[西原80]西原清一：
ハッシングの技法と応用、
情報処理、２１巻９号、980-991頁、1980.
６．２．３ ブロック構造と記号表
６．３ 属性文法
[Knut68] Knuth, D.E.:
Semantics of Context-Free Languages,
Math. Syst.Th., vol.2, no.2, pp.127-145, 1968.
訂正：Math. Syst.Th., vol.5, no.1, pp.95-96, 1971.
６．３．１ 属性文法の簡単な例
６．３．２ 属性文法の定義
６．３．３ 属性評価器
[Kata84] Katayama, T.:
Translation of Attribute Grammars into Procedures,
TOPLAS, vol.6, no.3, pp.345-369, 1984.
[Dera3-88] Deransart, P., Jourdan, M., and Lorho, B.:
Attribute Grammars -- Definitions, Systems and Bibliography,
LNCS 323, 1988.
６．３．４ １パス型属性文法
[徳田88] 徳田雄洋：
属性文法を効率的な動作ルーチンへ変換する方法について、
コンピュータソフトウェア、５巻２号、51-58頁、1988.
[Sass3-86] Sassa, M., Ishizuka, H. and Nakata, I.:
A Contribution to LR-attributed Grammars,
Journal of Information Processing, Vol.8, No.3, pp.196-206, 1986.
[Sass3-87] Sassa, M., Ishizuka, H. and Nakata, I.:
ECLR-attributed Grammars: a Practical Class of LR-attributed Grammars,
Information Processing Letters, Vol.24, No.1, pp.31-41, 1987.
６．３．５ 属性文法の拡張と応用
[Dera3-88] Deransart, P., Jourdan, M., and Lorho, B.:
Attribute Grammars -- Definitions, Systems and Bibliography,
LNCS 323, 1988.
[Paak95] Paakki, J.:
Attribute grammar paradigms - A high-level methodology in language implementation,
ACM Computing surveys, vol.27, no.2, pp.196-255, 1995.
[佐々3-93] 佐々政孝，石塚浩志，中田育男:
1パス型属性文法に基づくコンパイラ生成系Rie,
コンピュータソフトウェア, 10巻3号, 20-36頁, 1993.
[Wirt76] Wirth, N.:
Algorithms + Data Structures = Programs,
Prentice-Hall, 1976.
片山卓也訳：アルゴリズム＋データ構造＝プログラム、日本コンピュータ協会、1978.
[佐々89] 佐々政孝:
プログラミング言語処理系,
岩波講座ソフトウェア科学5, 岩波書店, 1989年.
[西野3-96] 西野哲朗、片山卓也、佐々政孝編、情報処理学会監修：
属性文法入門、
共立出版、1996年.
[Jull2-84] Jullig, R.K. and DeRemer,F.:
Regular Right-Part Attribute Grammars,
SIGPLAN NOTICES, Vol.19, No.6, pp.171-178, 1984.
[Kast3-82] Kastens, U., Hutt, B. and Zimmermann, E.:
GAG: A Practical Compiler Generator,
LNCS, Vol.141, 1982.
[丁4-89] 丁亜希, 渡辺美樹, 中田育男,佐々政孝:
正規右辺属性文法と１パス再帰降下属性評価器の生成,
情報処理学会論文誌, 30巻2号, pp.204-212, 1989.
[山之上2-85] 山之上卓，安在弘幸：
属性付構文翻訳系の生成系MYLANG，
情報処理学会論文誌，26巻1号，195-204頁、1985
[Elsw2-90] Elsworth, E.F., Parkers, M.A.B.:
Automated Compiler Construction based on Top-down Syntax Analysis and Attribute Evaluation,
SIGPLAN NOTICES, Vol.25, No.8, pp.37-42, 1990.
[中川5-95] 中川裕幸，金谷英信，星野英之，山下義行，中田育男：
拡張１パス型属性文法によるコンパイラ生成系の実現，
情報処理学会論文誌、３６巻４号、pp.902-912、1995.
[中田2-95] 中田育男，山下義行:
正規右辺属性文法の一提案,
情報処理学会論文誌, 36巻6号，1415-1421頁，1995年.
[Lamp98] Lampe, J.:
Depot4 -- A generator for dynamically extensible translators,
Software -- Concepts & Tools, vol.19, no.2, pp.97-108, 1998.
[Reps2-89] Reps, T.W. and Teitelbaum, T.:
The Synthesizer Generator,
Springer, 1989.
[Farr86] Farrow, R.:
Automatic Generation of Fixed-Point-Finding Evaluators for Circular, but Well-Defined, Attribute Grammars,
Compiler'86, pp.85-98, 1986.
７． 誤りの処理
７．１ 誤りの発見
７．１．１ 構文上の誤り
７．１．２ 意味上の誤り
７．２ 誤りの情報の出力
[Wirt76] Wirth, N.:
Algorithms + Data Structures = Programs,
Prentice-Hall, 1976.
片山卓也訳：アルゴリズム＋データ構造＝プログラム、日本コンピュータ協会、1978.
[中田95] 中田育男：
コンパイラ、
オーム社、1995年。
７．３ 誤りの修復
[Burk2-87] Burke, M.G. and Fisher G.A.:
A Practical Method for LR and LL Syntactic Error Diagnosis and Recovery,
TOPLAS, vol.9, no.2, pp.164-197, 1987.
[Char91] Charles, P.:
A Practical Method for Constructing Efficient LALR(k) Parsers with Automatic Error Recovery,
Ph.D thesis, New York University, May 1991.
[伊貝3-94] 伊貝 耕, 柴田 淳司, 中田 育男 :
構文エラーの分析と自動構文エラーリカバリアルゴリズムの評価,
情報処理学会 第47回全国大会講演論文集(分冊5), pp.71-72, 1994.
[Moss90] Mossenbock, H.:
Coco/R -- A Generator for Fast Compiler Front-Ends,
Report 127, Institute fur Computersysteme, ETH Zurich, 1990.
[Kast3-82] Kastens, U., Hutt, B. and Zimmermann, E.:
GAG: A Practical Compiler Generator,
LNCS, Vol.141, 1982.
７．４ 正常処理への復帰
[Cele78] Celentano, A.:
Incremental LR Parsers,
Acta Informatica, vol.10, pp.307-321, 1978.
[Jali2-82] Jalili, F. and Gallier, J.H.:
Building Friendly Parsers,
9-th POPL, pp.196-206, 1982.
[Yeh88] Yeh, D.:
Automatic Construction of Incremental LR(1)-Parsers,
SIGPLAN Notices, vol.23, no.3, pp.33-42, 1988.
[中井3-96] 中井央、山下義行、中田育男：
インクリメンタルなLR構文解析の一方式の提案とその評価、
情報処理学会論文誌, 37巻3号，371-383頁，1996年.
[Wagn2-98] Wagner, T.A., and Graham, S. L.:
Efficient and Flexible Incremental Parsing,
TOPLAS, vol.20, no.5, pp.980-1013, 1998.
[Yeh83] Yeh, D.:
On Incremental Evaluation of Ordered Attribute Grammars,
BIT, vol.23, pp.308-320, 1983.
[Reps3-83] Reps, T.W., Teitelbaum, T. and Demers, A.:
Incremental Context-Dependent Analysis for Language-Based Editors,
TOPLAS, vol.5, no.3, pp.449-477, 1983.
[Jali85] Jalili, F.:
A General Incremental Evaluator for Attribute Grammars,
Science of Computer Programming, vol.5, pp.83-96, 1985.
[中井4-96] 中井央、佐々政孝、山下義行、中田育男：
LR属性文法に基づいたインクリメンタルな属性評価、
情報処理学会論文誌, 37巻12号，2254-2265頁，1996年.
[Wirt76] Wirth, N.:
Algorithms + Data Structures = Programs,
Prentice-Hall, 1976.
片山卓也訳：アルゴリズム＋データ構造＝プログラム、日本コンピュータ協会、1978.
[Wirt86] Wirth, N.:
Compilerbau,
4th edition, Teubner Studienbucher, 1986.
[Moss90] Mossenbock, H.:
Coco/R -- A Generator for Fast Compiler Front-Ends,
Report 127, Institute fur Computersysteme, ETH Zurich, 1990.
[Schr2-85] Schreiner, A.T. and Friedman, H.G., Jr.:
Introduction to Compiler Construction with UNIX,
Prentice-Hall, 1985.
矢吹道郎、小暮博道、田中啓介訳：Cコンパイラ設計--yacc/lexの応用、啓学出版、1987.
８． 実行時記憶域と仮想マシン
８．１ 実行時記憶域
８．１．１ 基本データ型の表現
[Lind2-97] Lindholm, T., and Yellin, F.:
The Java Virtual Machine Specification,
Addison Wesley, 1997.
８．１．２ 配列型と構造体型の表現
８．１．３ クラスの表現
[Lind2-97] Lindholm, T., and Yellin, F.:
The Java Virtual Machine Specification,
Addison Wesley, 1997.
[小野寺97] 小野寺民也：
オブジェクト指向言語におけるメッセ−ジ送信の高速化技法，
情報処理，38巻4号，301-310頁，１９９７．
８．１．４ 手続き用の記憶域
[Lind2-97] Lindholm, T., and Yellin, F.:
The Java Virtual Machine Specification,
Addison Wesley, 1997.
８．２ 仮想マシンと通訳系
８．２．１ 仮想マシンとは
８．２．２ 仮想マシンの命令
[Nels79] Nelson, P.A.:
A Comparison of PASCAL Intermediate Languages,
Compiler'79, pp.208-213, 1979.
[Pemb2-82] Pemberton, S. and Daniels, M.C.:
Pascal Implementaion, The P4 Compiler,
Ellis Horwood, 1982.
武市正人、木村友則訳：Pascalの言語処理系 Pascal-P4、近代科学社、1984.
[Gold2-83] Goldberg, A. and Robson, D.:
Smalltalk-80 The Language and its Implementatrion,
Addison-Wesley, 1983.
[Gosl95] Gosling, J.:
Java Intermediate Bytecodes,
Proc. ACM SIGPLAN Workshop on Intermediate Representations (IR'95),
SIGPLAN Notices, vol.30, no.3, pp.111-118, 1995.
[Lipp96] Lippman, S.B.:
Inside the C++ Object Model,
Addison-Wesley, 1996.
三橋二彩子、佐治信之、原田賢一訳：C++ オブジェクトモデル、アジソン ウェスレイ・トッパン、1997.
[Lind2-97] Lindholm, T., and Yellin, F.:
The Java Virtual Machine Specification,
Addison Wesley, 1997.
[中田81b] 中田育男：
スタック・マシンのための最適コード生成のアルゴリズム、
情報処理学会論文誌、２２巻５号、pp.216-222、1981.
[Maie2-98] Maierhofer, M. and Ertl, M.A.:
Local Stack Allocation,
CC'98, pp.189-203, 1998.
８．２．３ 仮想マシン語への変換
８．２．４ 仮想マシンの実現（通訳系）
[Wirt76] Wirth, N.:
Algorithms + Data Structures = Programs,
Prentice-Hall, 1976.
片山卓也訳：アルゴリズム＋データ構造＝プログラム、日本コンピュータ協会、1978.
[中田95] 中田育男：
コンパイラ、
オーム社、1995年．
[Berr81] Berry, R.E.:
Programming Language Translation,
Ellis Horwood, 1981.
武市正人訳：プログラム言語の処理系、近代科学社、1983.
[Rees2-88] Rees, M. and Robson, D.:
Practical Compiling with Pascal-S,
Addison Wesley, 1988.
[Pemb2-82] Pemberton, S. and Daniels, M.C.:
Pascal Implementaion, The P4 Compiler,
Ellis Horwood, 1982.
武市正人、木村友則訳：Pascalの言語処理系 Pascal-P4、近代科学社、1984.
[Wels2-86] Welsh, J. and Hay, A.:
A Model Implementation of Standard Pascal,
Prentice-Hall, 1986.
[Gold2-83] Goldberg, A. and Robson, D.:
Smalltalk-80 The Language and its Implementatrion,
Addison-Wesley, 1983.
[Gosl95] Gosling, J.:
Java Intermediate Bytecodes,
Proc. ACM SIGPLAN Workshop on Intermediate Representations (IR'95),
SIGPLAN Notices, vol.30, no.3, pp.111-118, 1995.
[Lind2-97] Lindholm, T., and Yellin, F.:
The Java Virtual Machine Specification,
Addison Wesley, 1997.
９． 目的コードの生成
９．１ 中間語と機械語
[Stal92] Stallman, R.:
Using and Porting GNU CC,
Free Software Foundation, 1992.
９．２ 式のコ−ド生成
９．２．１ オペランド参照のコ−ド
９．２．２ 算術式のコ−ド
[Ersh58] Ershov, A.P.:
On Programming of Arithmetic Operations,
CACM, vol.1, no.8, pp.3-6, 1958.
[Naka67] Nakata, I. :
On Compiling Algorithms for Arithmetic Expressions,
CACM, vol.10, no.8, pp.492-494, 1967.
[Seth2-70] Sethi, R. and Ullman, J.D.:
The Generation of Optimal Code for Arithmetic Expressions,
J. ACM, vol.17, no.4, pp715-728, 1970.
[Aho3-77] Aho, A.V., Johnson, S.C., and Ullman, J.D.:
Code Generation for Expressions with Common Subexpressions,
J. ACM, vol.24, no.1, pp.146-160, 1977.
[Wulf5-75] Wulf, W.M., Johnsson, R.K., Weinstock, C.B., Hobbs, S.O., Geschke, C.M.:
The Design of an Optimizing Compiler,
American Elsevier, New York, 1975.
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
[中田77] 中田育男：
コンパイラにおける最適化の研究、
博士論文、東京大学、1977.
[Aho2-77b] Aho, A.V., and Sethi, R.:
How Hard is Compiler Code Generation,
LNCS 52 (Automata, Languages and Programming), pp.1-15, 1977.
[Brun2-75] Bruno, J. and Lassagne, T.:
The Generation of Optimal Code for Stack Machines,
J. ACM, vol.22, no.3, pp.382-396, 1975.
[中田81b] 中田育男：
スタック・マシンのための最適コード生成のアルゴリズム、
情報処理学会論文誌、２２巻５号、pp.216-222、1981.
９．３ 文のコ−ド生成
９．３．１ 分岐文のコ−ド
[中田75] 中田育男：
論理式のコンパイル方式、
情報処理、１６巻３号、pp.186-194、1975.
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
９．３．２ 手続き呼出しのコ−ド
９．３．３ 例外処理のコ−ド
[Chas94a] Chase, D.:
Implementation of Exception Handling, Part I,
The Journal of C Language Translation, vol.5, no.4, pp.229-240, 1994.
[Stro94] Stroustrup, B.:
The Design and Evolution of C++,
Addison-Wesley, 1994.
[Henn81] Hennessy, J.:
Program Optimization and Exception Handling,
8th POPL, pp.200-206, 1981.
[Chas94b] Chase, D.:
Implementation of Exception Handling, Part II: Calling Conventions, Asynchrony, Optimizers, and Debuggers,
The Journal of C Language Translation, vol.6, no.1, pp.20-32, 1994.
[Dean5-96] Dean, J., DeFouw, G., Grove, D., Litvinov, V., and Chambers, C.:
Vortex: An Optimizing Compiler for Object-Oriented Languages,
Proc. OOPSLA'96, ACM SIGPLAN Notices, vol.31, no.10, pp.83-100, 1996.
[Schi98] Schilling, J.L.:
Optimizing Away C++ Exception Handling,
ACM SIGPLAN Notices, vol.33, no.8, pp.40-47, 1998.
９．４ コ−ド生成器生成系
９．４．１ 木のパターンマッチングによるコード生成
[Catt80] Cattell, R.G.G.:
Automatic Derivation of Code Generators from Machine Description,
TOPLAS, vol.2, no.2, pp.173-190, 1980.
[Leve7-80] Leverett, B.W., Cattell, R.G.G., Hobbs, S.O., Newcomer, J.M., Reiner, A.H., Schatz, B.R., Wulf, W.A.:
An Overview of the Production Quality Compiler-Compiler Project,
IEEE Computer, vol.13, no.8, pp.38-49, 1980.
９．４．２ 構文解析法によるパターンマッチングでのコード生成
[Glan2-78] Glanville, R.S. and Graham, S.L.:
A New Method for Compiler Code Generation,
5-th POPL, pp.231-240, 1978.
[Grah80] Graham, S.L.:
Table-driven Code Generation,
IEEE Computer, vol.13, no.8, pp.25-34, 1980.
[Grah3-82] Graham, S.L., Henry, R.R., and Schulman, R.A.:
An Experiment in Table Driven Code Generation,
Compiler'82, pp.32-43, 1982.
[Craw82] Crawford, J.:
Engineering a Production Code Generator,
Compiler'82, pp.205-215, 1982.
[Aigr5-84] Aigrain, P., Graham, S.L., Henry, R.R., McKusick, M.K., Pelegri-Llopart, E.:
Experience with a Graham-Glanville Style Code Generator,
Compiler'84, pp.13-24, 1984.
[Gana2-85] Ganapathi, M., Fischer, C. N.:
Affix Grammar Driven Code Generation,
TOPLAS, vol.7, no.4, pp.560-599, 1985.
[三橋5-87] 三橋二彩子、佐治信之、石川浩之、保坂勇、藤林信也：
コード生成部生成ツールCOO、
情報処理学会論文誌 Vol.28, No.12, pp.1227-1236, 1987.
９．４．３ ダイナミックプログラミングによるコード生成
[Emme3-89] Emmelmann, H., Schroer, F.-W., and Landwehr, R.:
BEG -- A Generator for Efficient Back Ends,
PLDI'89, pp.227-237, 1989.
[Aho3-89] Aho, A.V., Ganapathi, M., and Tjiang, S.W.K.:
Code Generation Using Tree Matching and Dynamic Programming,
TOPLAS, vol.11, no.4, pp.491-516, 1989.
[Fras3-92a] Fraser, C.W., Henry, R.R. and Proebsting, T.A.:
BURG -- Fast Optimal Instruction Selection and Tree Parsing,
SIGPLAN Notices, vol.27, no.4, pp.68-76, 1992.
[Fras3-92b] Fraser, C.W., Hanson, D.R. and Proebsting, T.A.:
Engineering a Simple, Efficient Code Generator Generator,
ACM Letters on Programming Languages and Systems, vol.1, no.3, pp.213-226, 1992.
[Fras2-95] Fraser, C. W., and Hanson, D. R.:
A Retargetable C Compiler: Design and Implementation,
Benjamin/Cummings Publishing Co., 1995.
[Ertl99] Ertl, M.A.:
Optimal Code Selection in DAGs,
26-th POPL, pp.242-249, 1999.
９．５ 実行時コード生成
[Fran2-97] Franz, M. and Kistler, T.:
Slim Binaries,
CACM, vol.40, no.12, pp.87-94, 1997.
９．５．１ 動的コード生成
[Cons2-96] Consel, C. and Noel, F.:
A General Approach for Run-time Specialization and its Application to C,
23rd POPL, pp.145-156, 1996.
[Engl96] Engler, D. R.:
VCODE: A Retargetable, Extensible, Very Fast Dynamic Code Generation System,
PLDI '96, pp.160-170, 1996.
[Ausl5-96] Auslander, J., Philipose, M., Chambers, C., Eggers, S.J., and Bershad, B.N.:
Fast, Effective Dynamic Compilation,
PLDI'96, pp.149-159, 1996.
[藤波98] 藤波順久：
オブジェクト指向言語を利用した自動的かつ効率的な実行時コード生成、
コンピュータソフトウェア、vol.15, no.5, pp.25-37, 1998.
９．５．２ JITコンパイラ
[Kral2-97] Krall, A. and Grafl, R.:
CACAO -- A 64 bit JavaVM Just-in-Time Compiler,
Concurrency: Practice and Experience, vol.9, no.11, pp.1017-1030, 1997.
[Kral98] Krall, A.:
Efficient JavaVM Just-in-Time Compilation,
PACT'98, pp.205-212, 1998.
[Mats5-98] Matsuoka, S., Ogawa, H., Shimura, K., Kimura, Y., and Hotta, K.:
OpenJIT--A Reflective Java JIT Compiler,
Proc. OOPSLA'98 Workshop on Reflective Programming in C++ and Java, pp.16-20, 1998.
[wwwMsdk] http://www.microsoft.com/java/sdk/
[志村2-96] 志村浩也、木村康則：
Java JITコンパイラの試作、
情報処理学会研究会報告 96-ARC-120、37-42頁、1996.
[志村3-98] 志村浩也、河場基行、木村康則：
Javaの高速化、
第39回プログラミング・シンポジウム報告集、99-108頁、1998.
[Adl5-98] Adl-Tabatabai, A.-R., Cierniak, M., Lueh, G.-Y., Parikh, V.M., and Stichnoth, J.M.:
Fast, Effective Code Generation in a Just-In-Time Java Compiler,
PLDI'98, pp.280-290, 1998.
第３部 目的コードの最適化
１０．最適化とは
[Back-57] Backus, J.W. et al. :
The FORTRAN automatic coding system,
Proc. AFIPS 1957 WJCC, pp.188-198.
[Back78,81] Backus, J.W. :
The History of FORTRAN I, II, III,
SIGPLAN Notices, vol.13, no.8, Proc. History of Programming Languages Conf.,
pp.165-180, 1978.
History of Programming Languages,
Academic Press, pp.25-45, 1981.
[中田64] 中田育男, 高須昭輔, 稲富彬:
HITAC 5020ソフトウェアシステム(2) HARP 5020,
第５回プログラミングシンポジウム報告集，1964．
[中田87] 中田育男：
FORTRANコンパイラの開発,
コンピュ−タソフトウェア, 4巻1号, 53-64頁, 1987年1月
[Lowr-69] Lowry, E.S. et al. :
Object Code Optimization,
CACM, vol.12, no.1, pp.13-22, 1969.
１０．１ 最適化の例（行列の掛け算の例）
１０．１．１ 配列要素の配置と番地計算
１０．１．２ 最適化の例（スカラ計算機の場合）
１０．１．３ 最適化の例（アクセス効率とループ変換）
１０．１．４ 最適化の例（ベクトル計算機の場合）
１０．１．５ 最適化の例（並列計算機の場合）
１１．最適化の方法
１１．１ 命令の実行回数を減らす
１１．１．１ 共通部分式の削除
１１．１．２ 定数の畳み込み
１１．１．３ 命令のル−プの外への移動
１１．１．４ 部分冗長性の除去
１１．１．５ ル−プの変換
１１．１．６ 式の性質を利用して実行を省略する
１１．１．７ 無用命令の削除
１１．１．８ 複写の削除
１１．１．９ 手続き呼出しの特殊化
[小野寺97] 小野寺民也：
オブジェクト指向言語におけるメッセ−ジ送信の高速化技法，
情報処理，38巻4号，301-310頁，１９９７．
１１．１．１０ オブジェクトのインライン割当
[Dolb97] Dolby, J.:
Automatic Inline Allocation of Objects,
PLDI'97, pp.7-17, 1997.
[Dolb2-98] Dolby, J. and Chien, A.A.:
An Evaluation of Automatic Object Inline Allocation Techniques,
OOPSLA'98, SIGPLAN Notices, vol.33, no.10, pp.1-20, 1998.
１１．１．１１ 判定の置き換え
１１．１．１２ のぞき穴式最適化
１１．２ より速い命令の利用
１１．２．１ レジスタ割付け
１１．２．２ 特殊な命令の利用
１１．２．３ メモリアクセス順序の最適化（メモリ階層の有効利用）
１１．２．４ 演算の強さの軽減
１１．３ 並列度を上げる
[Bane4-93] Banerjee, U., Eigenmann, R., Nicolau, A., Padua, D.A.:
Automatic Program Parallelization,
Proceedings of the IEEE, vol.81, no.2, pp.211-243, 1993.
[Wolf96] Wolfe, M.:
High Performance Compilers for Parallel Computing,
Addison-Wesley, 1996.
１１．３．１ 命令レベル並列実行
１１．３．２ デ−タ並列実行
[Koel5-94] Koelbel, C.H., Loveman, D.B., Schreiber, R.S., Steele, G.L., Jr. and Zosel, M.E.:
The High Performance Fortran Handbook,
The MIT Press, 1994.
[HPF97] High Performance FORTRAN Forum,
High Performance FORTRAN Language Specification,
version 2.0, January 1997.
[HPF特集97] 特集：「HPF言語の動向」、
情報処理，38巻2号，85-120頁，1997.
[Mehr3-98] Mehrotra, P., Rosendale, J.V., Zima, H.:
High Performance Fortran: History, status and future,
Parallel Computing, vol.24, pp.325-354, 1998.
[wwwHPF] http://www.crpc.rice.edu/HPFF/home.html
[Humm3-92] Hummel, S.F., Schonberg, E., Flynn, L.E.:
Factoring: A Method for Scheduling Parallel Loops,
CACM, vol.35, no.8, pp.90-101, 1992.
[Hagh95] Haghighat, M.R.:
Symbolic Analysis for Parallelizing Compilers,
Kluwer Academic Publishers, 1995.
[Hira3-92] Hiranandani, S., Kennedy, K., Tseng, C-W.:
Compiling Fortran D for MIMD Distributed Memory Machines,
CACM, vol.35, no.8, pp.66-80, 1992.
１１．４ 最適化の方法の適用順序
[Much97] Muchnick, S.S.:
Advanced Compiler Design and Implementation,
Morgan Kaufmann, 1997.
[Wils11-94] Wilson, R. P, French, R. S., Wilson, C. S., Amarasinghe, S. P., Anderson, J. M., Tjiang, S. W. K., Liao, S., Tseng, C., Hall, M. W., Lam, M. S., Hennessy, J. L.:
SUIF: An Infrastructure for Research on Parallelizing and Optimizing Compilers,
ACM SIGPLAN Notices, Vol. 29, No. 12, pp.31-37, 1994.
[渡邊3-99] 渡邊坦、藤波順久、中田育男：
コンパイラ研究の動向について、
コンピュータソフトウェア、１６巻号、1999.
[wwwNCI] http://www.cs.virginia.edu/nci
[wwwSUIF] http://www-suif.stanford.edu/suif/
[wwwZep] http://www.cs.virginia.edu/zephyr/
１２．最適化のアルゴリズム
１２．１ 制御フロ−グラフ
１２．２ デ−タの流れの解析
１２．２．１ 共通部分式の削除（基本ブロックと拡張基本ブロック内）
１２．２．２ 変数の使用に対応する定義の解析
[Aho2-77] Aho, A.V. and Ullman, J.D.:
Principles of Compiler Design,
Addison Wesley, 1977.
土居範久他訳：コンパイラ，培風館，1986．
[Hech77] Hecht, M.S.:
Flow Analysis of Computer Programs,
North-Holland, 1977.
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
１２．２．３ デ−タの流れの等式の一般形
[Mart98] Martin, F.:
PAG -- an efficient program analyzer generator,
International Journal on Software Tools for Technology Transfer, vol.2, no.1, pp.46-67, 1998.
[wwwPAG] http://www.cs.uni-sb.de/~martin/pag/
１２．２．４ 共通部分式の削除（大域的）
１２．２．５ ループ
[Leng2-79] Lengauer, T. and Tarjan, R.E.:
A Fast Algorithm for Finding Dominators in a Flowgraph,
TOPLAS, vol.1, no.1, pp.121-141, 1979.
[Aho2-77] Aho, A.V. and Ullman, J.D.:
Principles of Compiler Design,
土居範久他訳：コンパイラ，培風館，1986．
[Hech77] Hecht, M.S.:
Flow Analysis of Computer Programs,
[中田81] 中田育男：
コンパイラ，
産業図書，1981．
[Aho3-86] Aho, A.V., Sethi, R., Ullman, J.D.:
Compilers -- Principles, Techniques, and Tools,
Addison Wesley, 1986.
原田賢一訳：コンパイラ 原理・技法・ツール I，II，サイエンス社，1990.
１２．２．６ ループの外への移動
１２．２．７ 変数の生と死の解析
１２．２．８ 無用命令の削除
１２．２．９ 定数伝播と畳み込み
１２．２．１０ 部分冗長性の除去
[More2-79] Morel, E. and Renvoise, C.:
Global Optimization by Suppression of Partial Redundancies,
CACM, vol.22, no.2, pp.96-103, 1979.
[Knoo3-94] Knoop, J., Ruething, O., and Steffen, B.:
Optimal Code Motion: Theory and Practice,
TOPLAS, vol.16, no.4, pp.1117-1155, 1994.
[Gupt2-99] Gupta, R. and Bodik, R.:
Register Pressure Sensitive Redundancy Elimination,
CC'99, LNCS 1575, pp.107-121, 1999.
[Stef96] Steffen, B.:
Property Oriented Expansion,
Proc. Int. Static Analysis Symposium (SAS'96), LNCS 1145, pp.22-41, 1996.
[Bodi3-98] Bodik, R., Gupta, R., and Soffa, M.L.:
Complete Removal of Redundant Computations,
PLDI'98, pp.1-14, 1998.
[Knoo3-99] Knoop, J., Ruething, O., and Steffen, B.:
Expansion-Based Removal of Semantic Partial Redundancies,
CC'99, LNCS 1575, pp.91-106, 1999.
１２．２．１１ 手続き間解析
[Weih80] Weihl, W.E.:
Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables,
7th POPL, pp.83-94, 1980.
[Much97] Muchnick, S.S.:
Advanced Compiler Design and Implementation,
Morgan Kaufmann, 1997.
[Coop2-88b] Cooper, K.D. and Kennedy, K.:
Interprocedural Side-Effect Analysis in Linear Time,
PLDI'88, pp.57-66, 1988.
[Coop2-84] Cooper, K.D. and Kennedy, K.:
Efficient Computation of Flow-Insensitive Interprocedural Summary Information ,
Compiler'84, pp.247-258, 1984.
[Coop2-88a] Cooper, K.D. and Kennedy, K.:
Efficient Computation of Flow-Insensitive Interprocedural Summary Information -- A Correction,
SIGPLAN Notices, vol.23, no.4, pp.35-42, 1988.
[Call88] Callahan, D.:
The Program Summary Graph and Flow-sensitive Interprocedural Data Flow Analysis,
PLDI'88, pp.47-56, 1988.
[Call4-86] Callahan, D., Cooper, K.D., Kennedy, K., Torczon, L.:
Interprocedural Constant Propagation,
Compiler'86, pp.152-161, 1986.
[Grov2-93] Grove, D., and Torczon, L.:
Interprocedural Constant Propagation: A Study of Jump Function Implementation,
PLDI'93, pp.90-99, 1993.
[Mart98] Martin, F.:
PAG -- an efficient program analyzer generator,
International Journal on Software Tools for Technology Transfer, vol.2, no.1, pp.46-67, 1998.
[Mart99] Martin, F.:
Experimental Comparison of Call String and Functional Approaches to Interprocedural Analysis,
CC'99, pp.63-75, 1999.
１２．２．１２ ポインタ解析
[Emam3-94] Emami, M., Ghiya, R. and Hendren L.J.:
Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers,
PLDI'94, pp.242-256, 1994.
[Deut94] Deutsch, A.:
Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting,
PLDI'94, pp230-241, 1994.
[Ghiy2-96a] Ghiya, R. and Hendren L.J.:
Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C,
23rd POPL, pp.1-15, 1996.
[Ghiy2-96b] Ghiya, R. and Hendren L.J.:
Connection Analysis: A Practical Interprocedural Heap Analysis for C,
International Journal of Parallel Programming, vol.24, no.6, pp.547-578, 1996.
[Ghiy2-98] Ghiya, R. and Hendren L.J.:
Putting Pointer Analysis to Work,
25th POPL, pp.121-133, 1998.
[Land2-92] Landi, W. and Ryder, B.G.:
A Safe Approximate Algorithm for Interprocedural Pointer Aliasing,
PLDI'92, pp.235-248, 1992.
[Burk4-94] Burke, M., Carini, P., Choi, J.-D., and Hind, M.:
Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers,
Proc. 7th International Workshop: Languages and Compilers for Parallel Computing, LNCS 892, pp.234-250, 1994.
[Stee96] Steensgaard, B.:
Points-to Analysis in Almost Linear Time,
23rd POPL, pp.32-41, 1996.
[Shap2-97] Shapiro, M. and Horowitz, S.:
Fast and Accurate Flow-Insensitive Points-To Analysis,
24th POPL, pp.1-14, 1997.
[Hast2-98] Hasti, R. and Horwitz, S.:
Using Static Single Assignment Form to Improve Flow-Insensitive Pointer Analysis,
PLDI'98, pp.97-105, 1998.
[Wils2-95] Wilson, R.P. and Lam, M.S.:
Efficient Context-sensitive Pointer Analysis for C Programs,
PLDI'95, pp.1-12, 1995.
[Ruf95] Ruf, E.:
Context-Insensitive Alias Analysis Reconsidered,
PLDI'95, pp.13-22, 1995.
１２．２．１３ 最適化の各操作の適用順序
[Cock2-80] Cocke, J. and Markstein, P.W.:
Measurement of Program Improvement Algorithms,
Information Processing 80, North-Holland, pp.221-228, 1980.
[Whit2-90] Whitefield, D. and Soffa, M.L.:
An Aproach to Ordering Optimizing Transformations,
2nd PPoPP (SIGPLAN Notices, vol.25, no.3), pp.137-146, 1990.
[Whit2-91] Whitefield, D. and Soffa, M.L.:
Automatic Generation of Global Optimizers,
PLDI'91, pp.120-129, 1991.
[Whit2-97] Whitefield, D. and Soffa, M.L.:
An Approach for Exploring Code-Improving Transformations,
TOPLAS, vol.19, no.6, pp.1053-1084, 1997.
[Coop3-99] Cooper, K.D., Schielke, P.J., and Subramanian, D.:
Optimizing for Reduced Code Space using Genetic Algorithms,
ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), pp.1-9, 1999.
[Wegm2-91] Wegman, M. N. and Zadeck, F. K. :
Constant Propagation with Conditional Branches,
TOPLAS, vol.13, no.2, pp.181-210, 1991.
[Clic2-95] Click, C. and Cooper, K. D. :
Combining Analysis, Combining Optimizations,
TOPLAS, vol.17, no.2, pp.181-196, 1995.
１２．３ 静的単一代入形式（SSA形式）
[Wolf96] Wolfe, M.:
High Performance Compilers for Parallel Computing,
Addison-Wesley, 1996.
[Chow6-97] Chow, F., Chan, S., Kennedy, R., Liu, S., Lo, R., Tu, P.:
A New Algorithm for Partial Redundancy Elimination based on SSA Form,
PLDI'97, pp.273-286, 1997.
１２．３．１ SSA形式の求め方
[Choi3-91] Choi, J.-D., Cytron, R. and Ferrante, J.:
Automatic Construction of Sparse Data Flow Evaluation Graphs,
18-th POPL, pp.55-66, 1991.
[Cytr5-91] Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.:
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph,
TOPLAS, vol.13, no.4, pp.451-490, 1991.
[Brig4-98] Briggs, P., Cooper, K.D., Harvey, T. J., and Simpson, L.T.:
Practical Improvements to the Construction and Destruction of Static Single Assignment Form,
Software--Practice and Experience, vol.28, no.8, pp.859-881, 1998.
[Wolf96] Wolfe, M.:
High Performance Compilers for Parallel Computing,
Addison-Wesley, 1996.
１２．３．２ 制御依存グラフとプログラム依存グラフ
[Ferr3-87] Ferrante, J., Ottenstein, K. J., and Warren, J. D. :
The Program Dependence Graph and its use in Optimization,
TOPLAS, vol.9, no.3, pp.319-349, 1987.
１２．３．３ 無用命令の削除
１２．３．４ 共通部分式の削除
[Clic95] Click, C.:
Global Code Motion Global Value Numbering,
PLDI'95, pp.246-257, 1995.
[Brig3-97] Briggs, P., Cooper, K.D., Simpson, L.T.:
Value Numbering,
Software--Practice and Experience, vol.27, no.6, pp.701-724, 1997.
[Alpe3-88] Alpern, B., Wegman, M.N., Zadeck, F.K.:
Detecting Equality of Variables in Programs,
15th POPL, pp.1-11, 1988.
[Aho3-74] Aho, A.V., Hopcroft, J.E., Ullman, J.D.:
The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
野崎，野下他訳：アルゴリズムの設計と解析 I，II，サイエンス社，1977.
[Coop3-95] Cooper, K., Simpson, T., Vick, C.:
Operator Strength Reduction,
Tech. Rept. CRPC-TR95635-S, Center for Research on Parallel Computation, Rice University, 1995.
１２．３．５ ループの外への移動
１２．３．６ 帰納変数
[Gerl3-95] Gerlek, M.P., Stoltz, E. and Wolfe, M.:
Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form,
TOPLAS, vol.17, no.1, pp.85-122, 1995.
１２．３．７ 演算の強さの軽減と判定の置き換え
[Coop3-95] Cooper, K., Simpson, T., Vick, C.:
Operator Strength Reduction,
Tech. Rept. CRPC-TR95635-S, Center for Research on Parallel Computation, Rice University, 1995.
１２．３．８ 定数伝播
１２．３．９ 部分冗長性の除去
[Chow6-97] Chow, F., Chan, S., Kennedy, R., Liu, S., Lo, R., Tu, P.:
A New Algorithm for Partial Redundancy Elimination based on SSA Form,
PLDI'97, pp.273-286, 1997.
[滝本2-97] 滝本宗宏，原田賢一：
拡張値グラフに基づく効果的な部分冗長除去法，
情報処理学会論文誌，38巻11号，pp.2237-2250，1997．
[Kenn6-98] Kennedy, R., Chow, F., Dahl, P., Liu, S.-M., Lo, R. and Streich, M.:
Strength Reduction via SSAPRE,
CC'98 (LNCS 1383), pp.144-158., 1998.
[Knoo3-94] Knoop, J., Ruething, O., Steffen, B.:
Optimal Code Motion: Theory and Practice,
TOPLAS, vol.16, no.4, pp.1117-1155, 1994.
１２．３．１０ ポインタ解析
[Hast2-98] Hasti, R. and Horwitz, S.:
Using Static Single Assignment Form to Improve Flow-Insensitive Pointer Analysis,
PLDI'98, pp.97-105, 1998.
[Lapk2-98] Lapkowski, C. and Hendren, L.J.:
Extended SSA Numbering: Introducing SSA Properties to Languages with Multi-level Pointers,
CC'98, pp.128-143, 1998.
１２．４ 命令スケジューリング（並列実行）
[Rau2-93] Rau, B.R. and Fisher, J.A.:
Instruction-level Parallel Processing: History, Overview, and Perspective,
J. Supercomputing, vol.7, pp.9-50, 1993.
[Alla4-95] Allan, V.H., Jones, R.B., Lee, R.M., Allan, S.J.:
Software Pipelining,
ACM Computing Surveys, vol.27, no.3, pp.367-432, 1995.
１２．４．１ 基本ブロック内の命令スケジューリング
[Brad3-91] Bradlee, D.G., Eggers, S.J., Henry, R.R.:
Integrated Register Allocation and Instruction Scheduling for RISCs,
Proc. 4th ASPLOS, pp.122-131, 1991.
[Pint93] Pinter, S.S.:
Register Allocation with Instruction Scheduling: a New Approach,
PLDI'93, pp.248-257, 1993.
[Bras4-95] Brasier, T.S., Sweany, P.H., Carr, S., Beaty, S.J.:
CRAIG: A Practical Framework for Combining Instruction Scheduling and Register Assignment,
Proc. IFIP WG10.3 Working Conf. on Parallel Architectures and Compilation Techniques, PACT'95, pp.11-18, 1995.
[Chen2-99] Chen, G. and Smith, M.D.:
Reorganizing Global Schedules for Register Allocation,
ICS'99, pp.408-416, 1999.
[Nova2-94] Novack, S. and Nicolau, A.:
Mutation Scheduling: A Unified Approach to Compiling for Fine-Grain Parallelism,
Proc. 7th Annual Workshop on Languages and Compilers for Parallel Computing, LNCS 892, pp.16-30, 1994.
[Nova97] Novack, S.:
The EVE Mutation Scheduling Compiler: Adaptive Code Generation for Advanced Microprocessors,
PhD thesis, University of California, Irvine, 1997.
[Kaes2-99] Kaestner, D. and Langenbach, M.:
Code Optimization by Integer Linear Programming,
CC'99, LNCS 1575, pp.122-136, 1999.
１２．４．２ 基本ブロックにまたがった命令スケジューリング
[Fish81] Fisher, J.A.:
Trace Scheduling: A Technique for Global Microcode Compaction,
IEEE Trans. Comput., vol.C-30, no.7, pp.478-490, 1981.
[Aike2-88] Aiken, A. and Nicolau, A.:
A Development Environment for Horizontal Microcode,
IEEE Trans. Soft. Eng., vol.14, no.5, pp.584-594, 1988.
[Hwu12-93] Hwu, W.-M.W., Mahlke, S.A., Chen, W.Y., Chang, P.P., Warter, N.J., Bringmann, R.A., Quellette, R.G., Hank, R.E., Kiyohara, T., Haab, G.E., Holm, J.G. and Lavery, D.M.:
The Superblock: An Effective Technique for VLIW and Superscalar Compilation,
The Journal of Supercomputing, vol.7, pp.229-248, 1993.
[Brow4-97] Brownhill, C.J., Nicolau, A., Novack, S. and Polychronopoulos, C.D.:
Achieving Multi-level Parallelization,
Proc. International Symposium on High Performance Computing (ISHPC), LNCS 1336, pp.183-194, 1997.
[Sait5-99] Saito, H., Stavrakos, N., Carroll, S., Polychronopoulos, C.D., Nicolau, A.:
The Design of the PROMIS Compiler,
CC'99, LNCS 1575, pp.214-228, 1999.
[Nico2-93] Nicolau, A. and Novack, S.:
Trailblazing: A Hierarchical Approach to Percolation Scheduling,
Proc. 1993 International Conference on Parallel Processing, vol.II, pp.120-124, 1993.
[Nova2-95] Novack, S. and Nicolau, A.:
A Hierarchical Approach to Instruction-level Parallelization,
International Journal of Parallel Programming, vol.23, no.1, pp.35-62, 1995.
[Ferr3-87] Ferrante, J., Ottenstein, K. J., and Warren, J. D. :
The Program Dependence Graph and its use in Optimization,
TOPLAS, vol.9, no.3, pp.319-349, 1987.
[Mahl5-92] Mahlke, S.A., Lin, D.C., Chen, W.Y., Hank, R.E., and Bringmann, R.A.:
Effective Compiler Support for Predicated Execution Using the Hyperblock,
MICRO 25, pp.45-54, 1992.
[Dehn3-89] Dehnert, J.C., Hsu, P.Y. and Bratt, J.P.:
Overlapped Loop Support in Cydra 5,
Proc. 3rd ASPLOS, pp.26-38, 1989.
[Alle4-83] Allen, J.R., Kennedy, K., Porterfield, C., and Warren, J.:
Conversion of Control Dependence to Data Dependence,
10th POPL, pp.177-189, 1983.
１２．４．３ ソフトウェア・パイプライニング
[Rau2-81] Rau, B.R., and Glaeser, C.D.:
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing,
Proc. 14th Annual Workshop on Microprogramming, pp.183-198, 1981.
[Alla4-95] Allan, V.H., Jones, R.B., Lee, R.M., Allan, S.J.:
Software Pipelining,
ACM Computing Surveys, vol.27, no.3, pp.367-432, 1995.
[Lam89] Lam, M.S.:
A Systolic Array Optimizing Compiler,
Kluwer Academic Pub., 1989.
[Lam88] Lam, M.S.:
Software Pipelining: An Effective Scheduling Technique for VLIW Machines,
PLDI'88, pp.318-328, 1988.
[Lela3-98] Lelait, S., Gao, G.R. and Eisenbeis, C.:
A New Fast Algorithm for Optimal Register Allocation in Modulo Scheduled Loops,
CC'98 (LNCS 1383), pp.204-218, 1998.
[Dehn3-89] Dehnert, J.C., Hsu, P.Y. and Bratt, J.P.:
Overlapped Loop Support in Cydra 5,
Proc. 3rd ASPLOS, pp.26-38, 1989.
[Rau4-92] Rau, B.R., Lee, M., Tirumalai, P.P., Schlansker, M.S.:
Register Allocation for Software Pipelined Loops,
PLDI'92, pp.283-299, 1992.
[Naka8-93] Nakamura, H., Imori, H., Nakazawa, K., Boku, T., Nakata, I., Yamashita, Y., Wada, H. and Inagami, Y.:
A Scalar Architecture for Pseudo Vector Processing based on Slide-Window Registers,
ICS'93, pp.298-307, 1993.
[中澤3-96] 中澤喜三郎，中村宏，朴泰祐：
超並列計算機CP-PACSのアーキテクチャ，
情報処理，３７巻１号，pp.18-28，1996．
[中田3-96] 中田育男，山下義行，小柳義夫：
超並列計算機CP-PACSのソフトウェア，
情報処理，３７巻，１号，pp.29-37，1996．
[山下2-95] 山下義行, 中田育男:
ソフトウェア・パイプライニングにおける多重ループの最適化，
並列処理シンポジウムJSPP'95, pp.185-192, 1995.
[Wang2-96] Wang, J. and Gao, G.R.:
Pipelining-Dovetailing: A Transformation to Enhance Software Pipelining for Nested Loops,
CC'96 (LNCS 1060), pp.1-17, 1996.
[Rutt4-96] Ruttenberg, J., Gao, G.R., Stoutchinin, A., Lichtenstein, W.:
Software Pipelining Showdown: Optimal vs. Heuristic Methods in a Production Compiler,
PLDI'96, pp.1-11, 1996.
１２．４．４ 条件文がある場合のソフトウェア・パイプライニング
[Lam88] Lam, M.S.:
Software Pipelining: An Effective Scheduling Technique for VLIW Machines,
PLDI'88, pp.318-328, 1988.
[Lam89] Lam, M.S.:
A Systolic Array Optimizing Compiler,
Kluwer Academic Pub., 1989.
[Dehn3-89] Dehnert, J.C., Hsu, P.Y. and Bratt, J.P.:
Overlapped Loop Support in Cydra 5,
Proc. 3rd ASPLOS, pp.26-38, 1989.
[Wart3-92] Warter, N.J., Haab, G.E. and Bockhaus, J.W.:
Enhanced Modulo Scheduling for Loops with Conditional Branches,
Proc. IEEE Micro-25, pp.170-179, 1992.
[Wart4-93] Warter, N.J., Mahlke, S.A., Hwu, W.W., Rau, B.R.:
Reverse IF-Conversion,
PLDI'93, pp.290-299, 1993.
[山下2-94] 山下義行, 中田育男:
ループ中に条件分岐を含む場合の最適なソフトウェア・パイプライニング，
並列処理シンポジウムJSPP'94, pp.17-24, 1994.
[糸賀4-99] 糸賀裕弥，秡川友宏，山下義行，中田育男：
条件分岐を考慮したソフトウェア・パイプライニングにおけるレジスタ割付，
並列処理シンポジウムJSPP'99, pp.39-46, 1999.
１２．４．５ 整数線形計画法によるソフトウェア・パイプライニング
[Eich2-97] Eichenberger, A.E., Davidson, E.S.:
Efficient Formulation for Optimal Modulo Schedulers,
PLDI'97, pp.194-205, 1997.
[Altm3-95a] Altman, E. R., Govindarajan, R., and Gao, G. R. :
An Experimental Study of an ILP-based Exact Solution Method for Software Pipelining,
Proc. 8th International Workshop, LCPC'95 (LNCS 1033, Languages and Compilers for Parallel Computing), pp.16-30, 1995.
[Altm3-95b] Altman, E.R., Govindarajan, R., Gao, G.R.:
Scheduling and Mapping: Software Pipelining in the Presence of Structural Hazards,
PLDI'95, pp.139-150, 1995.
[Govi3-96] Govindarajan, R., Altman, E.R., Gao, G.R.:
A framework for Resource-Constrained Rate-Optimal Software Pipelining,
IEEE Trans. Parallel and Distributed Sys., vol.7, no.11, pp.1133-1149, 1996.
[Rutt4-96] Ruttenberg, J., Gao, G.R., Stoutchinin, A., Lichtenstein, W.:
Software Pipelining Showdown: Optimal vs. Heuristic Methods in a Production Compiler,
PLDI'96, pp.1-11, 1996.
１２．５ レジスタ割付け
[Wall86] Wall, D.W.:
Global register allocation at link time,
Compiler'86, pp.264-275, 1986.
[Good97] Goodwin, D.W.:
Interprocedural Dataflow Analysisi in an Executable Optimizer,
PLDI'97, pp.122-133, 1997.
[Chow88] Chow, F.C.:
Minimizing register usage penalty at procedure calls,
PLDI'88, pp.85-94, 1988.
[Sant2-90] Santhanam, V. and Odnert, D.:
Register allocation across procedure and module boundaries,
PLDI'90, pp.28-39, 1990.
[Davi2-91] Davidson, J. W., Whalley, D. B.:
Methods for Saving and Restoring Register Values across Function Calls,
Software--Practice and Experience, vol.21, no.2, pp.149-165, 1991.
[Lueh2-97] Lueh, G.Y., Gross, T.:
Call-Cost Directed Register Allocation,
PLDI'97, pp.296-307, 1997.
１２．５．１ 簡単な割付け法
[Frei74] Freiburghouse, R.A.:
Register allocation via usage counts,
CACM, vol.17, no.11, pp.638-642, 1974.
[Fras2-92] Fraser, C.W. and Hanson, D.R.:
Simple Register Spilling in a Retargetable Compiler,
Software -- Practice and Experience, vol.22, no.1, pp.85-99, 1992.
[Trau3-98] Traub, O., Holloway, G., and Smith, M.D.:
Quality and Speed in Linear-scan Register Allocation,
PLDI'98, pp.142-150, 1998.
１２．５．２ 生存区間を使ったレジスタ割付け
[Hend4-92] Hendren, L.J., Gao, G.R., Altman, E.R, Mukerji, C.:
A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs,
4th International Workshop on Compiler Construction CC'92 (LNCS 641), pp.176-191, 1992.
[Hend4-93] Hendren, L.J., Gao, G.R., Altman, E.R, Mukerji, C.:
A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs,
McGill University, ACAPS Technical Memo 33 (Revised), 1993.
[Ning2-93] Ning, Q. and Gao, G.R.:
A Novel Framework of Register Allocation for Software Pipelining,
POPL'93, pp.29-42, 1993.
[Eise3-95] Eisenbeis, C., Lelait, S., Marmol, B.:
The meeting graph: a new model for loop cyclic register allocation,
Proc. IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, PACT'95, pp.264-267, 1995.
[秡川4-98] 秡川友宏，添野元秀，山下義行，中田育男:
スライドウィンドウを考慮したレジスタ割付,
情報処理学会論文誌, 39巻9号，2684-2694頁，1998.
[秡川4-97] 秡川友宏，添野元秀，山下義行，中田育男:
レジスタ割付からみたスライドウィンドウの優位性について,
情報処理学会第55回全国大会講演論文集(1)，16-17頁，1997.
１２．５．３ 生存区間の干渉グラフを使ったレジスタ割付け
[Chai6-81] Chaitin, G. J., Auslander , M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. W.:
Register Allocation via coloring,
Computer Languages, vol.6, no.1, pp.47-57, 1981.
[Chai82] Chaitin, G. J. :
Register Allocation and Spilling via graph coloring,
Compiler'82, SIGPLAN Notices vol.17, no.6, pp.98-105, 1982.
[Chow2-84] Chow, F.C. and Hennessy, J.L. :
Register Allocation by Priority-Based Coloring,
Compiler'84, pp.222-232, 1984.
[Chow2-90] Chow, F.C. and Hennessy, J.L. :
The Proirity-Based Coloring approach to Register Allocation,
TOPLAS, vol.12, no.4, pp.501-536, 1990.
[Coop2-98] Cooper, K.D., Simpson, L.T.:
Live Range Splitting in a Graph Coloring Register Allocator,
CC'98 (LNCS 1383), pp.174-187, 1998.
[Bern7-89] Bernstein, D., Goldin, D.Q., Golumbic, M.C., Krawczyk, H., Mansour, Y., Nahshon, I., Pinter, R.Y.:
Spill code minimization techniques for optimizing compilers,
PLDI'89, pp.258-263, 1989.
[Brig3-94] Briggs, P., Cooper, K. D., and Torczon, L. :
Improvements to graph coloring register allocation,
TOPLAS, vol.16, no.3, pp.428-455, 1994.
[Berg4-97] Bergner, P., Dahl, P., Engebretsen, D., O'Keefe, M.:
Spill Code Minimization via Interference Region Spilling,
PLDI'97, pp.287-295, 1997.
[Geor2-96] George, L. and Appel, A. W. :
Iterated Register Coalescing,
23rd POPL, pp.208-218, 1996.
TOPLAS, vol.18, no.3, pp.300-324, 1996.
[Gupt3-89] Gupta, R., Soffa, M.L., Steele, T.:
Register Allocation via Clique separators,
PLDI'89, pp.264-274, 1989.
[Call2-91] Callahan, D. and Koblenz, B.:
Register Allocation via Hierarchical Graph Coloring,
PLDI'91, pp.192-203, 1991.
[Coop3-98] Cooper, K.D., Harvey, T.J., Torczon, L.:
How to Build an Interference Graph,
Software--Practice and Experience, vol.28, no.4, pp.425-444, 1998.
[Park2-98] Park, J. and Moon, S.-M.:
Optimistic Register Coalescing,
PACT'98, pp.196-204, 1998.
[Vegd99] Vegdahl, S.R.:
Using Node Merging to Enhance Graph Coloring,
PLDI'99, pp.150-154, 1999.
１２．５．４ 整数線形計画法によるレジスタ割付け
[Good2-96] Goodwin, D.W. and Wilken K.D.:
Optimal and Near-optimal Global Register Allocation Using 0-1 Integer Programming,
Software--Practice and Experience, vol.26, no.8, pp.929-965, 1997.
１２．６ 配列要素の依存解析
１２．６．１ データの依存関係
１２．６．２ １重ループ内の依存関係とベクトル化
１２．６．３ 多重ループにおける依存関係
１２．６．４ データ依存関係の解析法
[Bane88] Banerjee, U.:
Dependence Analysis for Supercomputing,
Kluwer Academic Publishers, 1988.
[Pugh92] Pugh, W.:
A Practical Algorithm for Exact Array Dependence Analysis,
CACM, vol.35, no.8, pp.102-114, 1992.
[Zima2-90] Zima, H. and Chapmen, B.:
Supercompilers for Parallel and Vector Computers,
ACM Press, Addison-Wesley, 1990.
村岡洋一訳：スーパコンパイラ，オーム社，1995.
[Pugh91] Pugh, W.:
The Omega Test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis,
Supercomputing '91, pp.4-13, 1991.
[Wolf96] Wolfe, M.:
High Performance Compilers for Parallel Computing,
Addison-Wesley, 1996.
[wwwOME] http://www.cs.umd.edu/projects/omega/
１２．７ ループ変換
１２．７．１ ループ分配
[Alle2-87] Allen, R. and Kennedy, K.:
Automatic Translation of FORTRAN Programs to Vector Form,
TOPLAS, vol.9, no.4, pp.491-592, 1987.
[Sark97] Sarkar, V.:
Automatic selection of high-order transformations in the IBM XL FORTRAN compilers,
IBM Journal of Research and Development, vol.41, no.3, pp.233-264, 1997.
１２．７．２ ループ融合
１２．７．３ ループ交換
[Wolf2-91] Wolf, M.E., and Lam, M.S.:
A Loop Transformation Theory and an Algorithm to Maximize Parallelism,
IEEE Trans. Parallel & Distributed Syst., vol.2, no.4, pp.452-471, 1991.
１２．７．４ ループ逆転
１２．７．５ ループ傾斜
１２．７．６ 波頭変換
[Wolf2-91] Wolf, M.E., and Lam, M.S.:
A Loop Transformation Theory and an Algorithm to Maximize Parallelism,
IEEE Trans. Parallel & Distributed Syst., vol.2, no.4, pp.452-471, 1991.
１２．７．７ ループ細分
１２．７．８ ループタイル化
[Lam3-91] Lam, M.S., Rothberg, E.E., and Wolf, M.E.:
The Cache Performance and Optimizations of Blocked Algorithms,
ASPLOS-IV Proceedings, pp.63-74, 1991.
[Cole2-95] Coleman, S. and McKinley, K.S.:
Tile Size Selection Using Cache Organization and Data Layout,
PLDI'95, pp.279-290, 1995.
[Wolf3-96] Wolf, M.E., Maydan, D.E., and Chen, D.-K.:
Combining Loop Transformations Considering Caches and Scheduling,
MICRO 29, pp.262-273, 1996.
[Sark97] Sarkar, V.:
Automatic selection of high-order transformations in the IBM XL FORTRAN compilers,
IBM Journal of Research and Development, vol.41, no.3, pp.233-264, 1997.
[Rive2-99] Rivera, G. and Tseng, C.-W.:
A Comparison of Compiler Tiling Algorithms,
CC'99, LNCS 1575, pp.168-182, 1999.
[Cham2-99] Chame, J. and Moon, S.:
A Tile Selection Algorithm for Data Locality and Cache Interference,
ICS'99, pp.492-499, 1999.
[Kodu3-97] Kodukula, I., Ahmed, N. and Pingali, K.:
Data-centric Multi-level Blocking,
PLDI'97, pp.346-357, 1997.
[Kodu4-99] Kodukula, I., Pingali, K., Cox, R., Maydan, D.:
Experimental Evaluation of Tiling and Shackling for Memory Hierarchy Management,
ICS'99, pp.482-491, 1999.
[Song2-99] Song, Y. and Li, Z.:
New Tiling Techniques to Improve Cache Temporal Locality,
PLDI'99, pp.215-228, 1999.
[Ohta4-95] Ohta, H., Saito, Y., Kainaga, M., and Ono, H.:
Optimal Tile Size Adjustment in Compiling General DOACROSS Loop Nests,
ICS'95, pp.270-279, 1995.
[石崎2-97] 石崎一明，小松秀昭:
分散メモリ並列計算機のためのコンパイラによる通信遅延隠蔽アルゴリズム,
情報処理学会論文誌，38巻9号，1849-1858頁，1997.
１２．７．９ ループ展開
１２．７．１０ ループ合体
１２．７．１１ ループつぶし
１２．７．１２ ループ皮むき
１２．７．１３ ループ変換の適用順序
１２．８ データ分散と通信
[Gupt92] Gupta, M.:
Automatic Data Partitioning on Distributed Memory Multicomputers,
PhD Thesis, University of Illinois, Urbana-Champaign, 1992.
[Chat3-93] Chatterjee, S., Gilbert, J.R., and Schreiber, R.:
The alignment-distribution graph,
LNCS 768, Langages and Compilers for Parallel Computing (Proc. 6th InternationalWorkshop), pp.234-252, 1993.
[Chat4-93] Chatterjee, S., Gilbert, J.R., Schreiber, R., and Teng, S.-H.:
Automatic array alignment in data-parallel programs,
20-th POPL, pp.16-28, 1993.
[Ande2-93] Anderson, J.M. and Lam, M.S.:
Global Optimizations for Parallelism and Locality on Scalable Parallel Machines,
PLDI'93, pp.112-125, 1993.
[Bau5-94] Bau, D., Kodukula, I., Kotlyar, V., Pingali, K., Stodghill, P.:
Solving Alignment using Elementary Linear Algebra,
LNCS 892, Langages and Compilers for Parallel Computing (Proc. 7th InternationalWorkshop), pp.46-60, 1994.
[Mukh2-99] Mukherjee, N. and Gurd, J.R.:
A Comparative Analysis of Four Parallelisation Schemes,
ICS'99, pp.278-285, 1999.
[Kenn2-98] Kennedy, K. and Kremer, U.:
Automatic Data Layout for Distributed-Memory Machines,
TOPLAS, vol.20, no.4, pp.869-916, 1998.
１２．８．１ 各プロセッサでの私物化
[Feau91] Feautrier, P.:
Dataflow analysis of array and scalar references,
International Journal of Parallel Programming, vol.20, no.1, pp.23-53, 1991.
[Li92] Li, Z.:
Array privatization for parallel execution of loops,
ICS'92, pp.313-322, 1992.
[Mayd3-93] Maydan, D.E., Amarasinghe, S.P., and Lam, M.S.:
Array Data Flow Ananysis and its use in Array Privatization,
20-th POPL, pp.1-15, 1993.
[Tu2-93] Tu, P. and Padua, D.:
Automatic Array Privatization,
LNCS 768, Langages and Compilers for Parallel Computing (Proc. 6th InternationalWorkshop), pp.500-521, 1993.
[Bart3-98] Barthou, D., Cohen, A., and Collard, J.-F.:
Maximal Static Expansion,
25-th POPL, pp.98-106, 1998.
１２．８．２ 配列分散の解析
１２．８．３ 計算分散の解析
１２．８．４ 通信の解析
[Hanx2-94] Hanxleden, R. and Kennedy, K.:
Give-N-Take -- A Balanced Code Placement Framework,
PLDI'94, pp.107-120, 1994.
[Gupt4-96] Gupta, S.K.S., Kaushik, S.D., Huang, C.-H., and Sadayappan, P.:
Compiling Array Expressions for Efficient Execution on Distributed-Memory Machines,
Journal of Parallel and Distributed Computing, vol.32, pp.155-172, 1996.
[太田2-98] 太田寛，西谷康仁：
データ並列言語における多重ループの計算分散方式，
並列処理シンポジウムJSPP'99，79-86頁，1999.
１２．８．５ 通信の最適化
１２．８．６ デ−タ分散の自動化
[Bala4-91] Balasundaram, V., Fox, G., Kennedy, K., and Kremer, U.:
A Static Performance Estimator to Guide Data Partitioning Decisions,
3rd PPoPP, pp.213-223, 1991.
[Gupt92] Gupta, M.:
Automatic Data Partitioning on Distributed Memory Multicomputers,
PhD Thesis, University of Illinois, Urbana-Champaign, 1992.
[Gupt2-93] Gupta, M. and Banerjee, P.:
PARADIGM: A Compiler for Automatic Data Distribution on Multicomputers,
ICS'93, pp.87-96, 1993.
[Ande2-93] Anderson, J.M. and Lam, M.S.:
Global Optimizations for Parallelism and Locality on Scalable Parallel Machines,
PLDI'93, pp.112-125, 1993.
[Krem95] Kremer, U.:
Automatic Data Layout for Distributed Memory Machines,
PhD Thesis, crpc-tr95-559-s, Center for Research on Parallel Computation, Rice University, 1995.
[Dier3-96] Dierstein, A., Hayer, R., and Rauber, T.:
The ADDAP System on the iPSC/860: Automatic Data Distribution and Parallelization,
Journal of Parallel and Distributed Computing, vol.32, pp.1-10, 1996.
[Lee97] Lee, P.:
Efficient Algorithms for Data Distribution on Distributed Memory Parallel Computers,
IEEE Trans. on Parallel and Distributed Systems, vol.8, no.8, pp.825-839, 1997.
[Kenn2-98] Kennedy, K. and Kremer, U.:
Automatic Data Layout for Distributed-Memory Machines,
TOPLAS, vol.20, no.4, pp.869-916, 1998.
[松浦4-99] 松浦健一郎，村井均，末廣謙二，妹尾義樹：
データ並列プログラムに対する高速な自動データ分割手法，
並列処理シンポジウムJSPP'99，87-94頁，1999．
[Chen2-94] Chen, T.-S. and Sheu, J.-P.:
Communication-Free Data Allocation Techniques for Parallelizing Compilers on Multicomputers,
IEEE Trans. Parallel and Distributed Computing, vol.5, no.9, pp.924-938, 1994.
[Li2-91] Li, J. and Chen, M.:
The Data Alignment Phase in Compiling Programs for Distributed-Memory Machines,
Journal of Parallel and Distributed Computing, vol.13, pp.213-221, 1991.
[Lim2-97] Lim, A.W. and Lam, M.S.:
Maximizing Parallelism and Minimizing Synchronization with Affine Transforms,
24th POPL, 1997.
[Lim2-98] Lim, A.W. and Lam, M.S.:
Maximizing Parallelism and Minimizing Synchronization with Affine Partitions,
Parallel Computing, vol.24, no.3-4, pp.445-475, 1998.
[Lim3-99] Lim, A.W., Cheong, G.I. and Lam, M.S.:
An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication,
ICS'99, pp.228-237, 1999.
[Rama2-95] Ramaswamy, S. and Banerjee, P.:
Automatic Generation of Efficient Array Redistribution Routines for Distributed Memory Multicomputers,
Frontiers'95: The Fifth Symposium on the Frontiers of Massively Parallel Computation,McLean, VA, pp.342-349, 1995.
[Rama3-96] Ramaswamy, S., Simons, B., and Banerjee, P.:
Optimizations for Efficient Array Redistribution on Distributed Memory Multicomputers,
Journal of Parallel and Distributed Computing, vol.38, pp.217-228, 1996.
[Thak3-96] Thakur, R., Choudhary, A., and Ramanujam, J.:
Efficient Algorithms for Array Redistribution,
IEEE Transactions on Parallel and Distributed Systems, vol.7, no.6, pp.587-593, 1996.
[Coel2-96] Coelho, F. and Ancourt, C.:
Optimal Compilation of HPF Remappings,
Journal of Parallel and Distributed Computing, vol.38, pp.229-236, 1996.
[Pale3-96] Palermo, D.J., Hodges IV, E.W., and Banerjee, P.:
Dynamic Data Partitioning for Distributed-Memory Multicomputers,
Journal of Parallel and Distributed Computing, vol.38, pp.158-175, 1996.
[Chun3-98] Chung, Y.-C., Hsu, C.-H., and Bai, S.-W.:
A Basic-Cycle Calculation Technique for Efficient Dynamic Data Redistribution,
IEEE Transactions of Parallel and Distributed Systems, vol.9, no.4, pp.359-377, 1998.
[Guo3-98a] Guo, M., Yamashita, Y., Nakata, I.:
Improving Performance of Multi-dimensional Array Redistribution on Distributed Memory Machines,
Proc. Third International Workshop on High-Level Parallel Programming Models and Supportive Environments, Orlando, Florida, pp.82-91, 1998.
[Kaus4-94] Kaushik, S.D., Huang, C.-H., Johnson, R.W., and Sadayappan, P.:
An Approach to Communication-Efficient Data Redistribution,
ICS'94, pp.364-373, 1994.
[Lim3-97] Lim, Y.W., Park, N., and Prasanna, V.:
Efficient Algorithms for Multi-dimensional Block-Cyclic Redistribution of Arrays,
Proc. 26th International Conference on Parallel Processing, Bloomingdale, IL, Aug. 1997.
[Desp5-98] Desprez, F., Dongarra, J., Petitet, A., Randriamaro, C. and Robert, Y.:
Scheduling Block-Cyclic Array Redistribution,
IEEE Transactions on Parallel and Distributed Systems, vol.9, no.2, pp.192-205, 1998.
[Guo3-98b] Guo, M., Nakata, I., and Yamashita, Y.:
Contention-Free Communication Scheduling for Array Redistribution,
Proc. 1998 International Conference on Parallel and Distributed Systems, Tainan, Taiwan, pp.658-667, Dec. 1998.
１２．８．７ 配列へのアクセスが規則的でない場合
[窪田6-94] 窪田昌史，三吉郁夫，大野和彦，森真一郎，中島浩，富田真治：
不規則アクセスを伴うループの並列化コンパイル技法
一 Inspector/Executorアルゴリズムの高速化 一，
情報処理学会論文誌，３５巻４号，532-541頁，1994
[Koel2-91] Koelbel, C. and Mehrotra, P.:
Compiling Global Name-Space Parallel Loops for Distributed Execution,
IEEE Trans. Parallel and Distributed Syst., vol.2, no.4, pp.440-451, 1991.
[Rauc2-94] Rauchwerger, L. and Padua, D.:
The Privatizing DOALL Test: A Run-Time Technique for DOALL Loop Identification and Privatization,
ICS'94, pp.33-43, 1994.
[Rauc2-95] Rauchwerger, L. and Padua, D.:
The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization,
PLDI'95, pp.218-232, 1995.
[Pate2-99] Patel, D. and Rauchwerger, L.:
Implementation Issues of Loop-Level Speculative Run-Time Parallelization,
CC'99, LNCS 1575, pp.183-197, 1999.
[Rauc2-99] Rauchwerger, L. and Padua, D.:
The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization,
IEEE Trans. Parallel and Distributed Systems, vol.10, no.2, pp.160-180, 1999.
参考文献
文献の略記法
CC'nn: Proceedings of International Conference of Compiler Construction held in 19nn
Compiler'nn: Proceedings of the ACM SIGPLAN'nn Symposium on Compiler Construction
PLDI'nn: Proceedings of the ACM SIGPLAN'nn Conference on Programming Language Design and Implementation
TOPLAS: ACM Transactions on Programming Languages and Systems
CACM: Communications of the ACM
n-th PPoPP: Proceedings of the n-th ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
n-th POPL: Conference Record of the n-th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
ASPLOS: Architectural Support for Programming Languages and Operating Systems
LNCS: Lecture Notes in Cmputer Science, Springer-Verlag
ICS'xx: Conference Proceedings, 19xx International Conference of Supercomputing
PACT'nn: Proceedings 19nn International Conference on Parallel Architecture and Compilation Techniques