twk@cadence.com (Tom Kronmiller) (02/09/90)
After years of working on hardware design tools, I have become involved with
theoretical and practical aspects of implementing highly optimizing compilers.
In hardware CAD, it is frequently the case that the tools run for many CPU
hours, and this makes the customers unhappy. They would like to have
the software run in much less time. One of the things this suggests
is that the software should be made to run on parallel hardware.
In evaluating the cost/benefit ratio of parallelization, the question of
whether compilers can do the optimization for us arose, along with the
question of how well a compiler could do the job. This rekindled
my personal interest in the field of compilation, so I have been trying to
learn about the state of the art in parallelizing/pipelining compilers.
My request has two parts:
1. If anyone knows of good references to papers discussing theory
and practice, please advise me. Especially the practical aspects,
such as good data structures for representing programs (large
programs, by the way), successful heuristics for transforming the code
and empirically tested rules for ordering their application,
expected amounts of memory and MIPS required, expected degree
of pipelining or parallelizing to be attained, etc. I would take
on-line copies of papers, too.
2. I'd also like to know who are the true experts in this area; i.e.,
people with strong theoretical backgrounds, or especially people who
have successfully implemented highly optimizing compilers for some of
the newer pipelined RISC machines, or (say) the i860 or a hyper-cube.
I am interested in learning about their experiences with the various
newer architectures. I'm also interested in their opinions about manual
vs. automated pipelining/parallelizing.
Any information will be gratefully appreciated. Please reply via e-mail.
Thanks!
Thomas W. Kronmiller twk@cadence.com
Manager, System Architecture
Software Development Environment Ph. 408-987-5479
Cadence Design Systems, Inc. FAX 408-727-5049
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.scott@cs.rochester.edu (Michael Scott) (02/10/90)
The following is a bibliography I threw together for a graduate seminar
in back-end compiler technology. I make ABSOLUTELY NO CLAIMS about
coverage, balance, accuracy, or whatever (as I said, it was thrown together),
but this may nonetheless be of some use to the poster, or to others.
Thanks to Cesar Quiroz for providing many of the citations.
General Compiler Books
[ ] A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles,
Techniques, and Tools, Addison-Wesley, Reading, MA, 1986.
[ ] A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation,
and Compiling, Vol 2: Compiling, Prentice-Hall, 1973.
[ ] J. Cocke and J. T. Schwartz, Programming Languages and Their
Compilers, Courant Institute of Mathematical Sciences, 1970.
[ ] C. N. Fischer and R. J. LeBlanc, Crafting a Compiler,
Benjamin/Cummings, Menlo Park, CA, 1988.
[ ] David Gries, Compiler Construction for Digital Computers, John
Wiley, 1971.
[ ] Jean-Paul Tremblay and Paul G. Sorenson, The Theory and Prac-
tice of Compiler Writing, McGraw-Hill Inc., 1984.
[ ] W. A. Wulf, R. K. Johnson, C. B. Weinstock, S. O. Hobbs, and C.
M. Geschke, The Design of an Optimizing Compiler, Elsevier
North-Holland, NY, 1975.
Simple Optimizations
[ ] D. R. Hanson, "Simple Code Optimizations," Software - Practice
and Experience 13 (1983), pp. 745-763.
[ ] Michael L. Powell, "A Portable Optimizing Compiler for Modula-
2," Proceedings of the SIGPLAN'84 Symposium on Compiler Con-
struction, ACM, 1984, pp. 310-318.
Miscellaneous
[ ] F. E. Allen, "Program Optimization," Annual Review of Automatic
Programming 5 (1969), pp. 239-307.
[ ] Utpal Banerjee, "Speedup of Ordinary Programs," UIUCDS-R-79-
989, U of Illinois at Urbana-Champaign, Oct 1979.
[ ] David Bernstein, Haran Boral, and Ron Y. Pinter, "Optimal
Chaining in Expression Trees," IEEE Transactions on Computers
37:11 (November 1988), pp. 1366-1374.
[ ] V. A. Busam and D. E. Englund, "Optimization of expresions in
Fortran," CACM 12:12 (1969), pp. 666-674.
[ ] J. Cocke, "Global common subexpression elimination," SIGPLAN
notices 5:7, ACM (1970), pp. 20-24.
[ ] J. Cocke and K. Kennedy, "An Algorithm for Reduction of Opera-
tor Strength," CACM 20:11 (), pp. 850-856.
[ ] D. S. Coutant, C. L. Hammond, and J. W. Kelley, "Compilers for
the New Generation of Hewlett-Packard Computers," Hewlett-
Packard Journal, 1986, pp. 4-18.
[ ] Dhananjay Madhav Dhamdere and Jatinder Singh Keith, "Character-
ization of Program Loops in Code Optimization," Computer
Languages 8, Pergammon Press Ltd (1983), pp. 69-76.
[ ] Samuel P. Harbison, "A Computer Architecture for the Dynamic
Optimization of High-Level Language Programs," CMU-CS-80-143,
Computer Science Dept., Carnegie-Mellon University, September
1980.
[ ] D. E. Knuth, "An empirical study of FORTRAN programs," Software
- Practice and Experience 1:12 (1971.), pp. 105-134.
[ ] John M. Levesque and Joel W. Williamson, A Guidebook to Fortran
on Supercomputers, Academic Press, NY, 1988.
[ ] E. S. Lowry and C. W. Medlock, "Object Code Optimization," CACM
12:1 (January 1969), pp. 13-22.
[ ] Ikuo Nakata, "On Compiling Algorithms for Arithmetic Expres-
sions," CACM 10:8 (), pp. 492-494.
[ ] L. Pollock and M. L. Soffa, "Incremental Compilation of Locally
Optimized Code," pp. 152-164 in Conference Record of the
Twelfth ACM Symposium on Principles of Programming Languages,
Jan. 1985.
[ ] Marc Sabatella, "Barking Up The Wrong Tree: Why Optimizing Com-
pilers Are Still Unable To Match Assembly Language," Report
UCB/CSD 88/428, Computer Science Division (EECS), University of
California, Berkeley, Berkeley, California 94720, August 1988.
[ ] J. D. Ullman, "Fast Algorithms for the Elination of Common
Subexpressions," Acta Informatica 2:3 (1973), pp. 191-213.
[ ] N. Wirth, "From Programming Language Design to Computer Con-
struction," CACM 28:2 (February 1985), pp. 159-164. The 1984
Turing Award Lecture.
Code Generation
[ ] A. V. Aho, S. C. Johnson, and J. D. Ullman, "Code Generation
for Machines with Multiregister Operations," pp. 21-28 in 4th
ACN Symposium of Principles of Programming Languages.
[ ] A. V. Aho, S. C. Johnson, and J. D. Ullman, "Code Generation
for Expressions with Common Subexpressions," JACM 24:1 (), pp.
146-160.
[ ] J. Bruno and R. Sethi, "Code Generation for a One-Register
Machine," JACM 23:3 (), pp. 502-510.
[ ] F. Chow, S. Correll, M. Himelstein, E. Killian, and L. Weber,
"How Many Addressing Modes are Enough?," SIGPLAN Notices,
Proceedings of ASPLOS II 22:10, Computer Society Press of the
IEEE (October 5-8, 1987), pp. 117-121. Also sponsored by ACM's
SIGARCH, SIGPLAN, and SIGOPS.
[ ] C. W. Fraser and A. L. Wendt, "Integrating Code Generation and
Optimization," Proceeding of the SIGPLAN '86 Symposium on Com-
piler Construction, 25-27 June 1986, pp. 242-248. In ACM SIG-
PLAN Notices 21:7 (July 1986).
[ ] M. Ganapathi, C. N. Fischer, and J. L. Hennessy, "Retargetable
Compiler Code Generation," ACM Computing Surveys 14:4 (December
1982), pp. 573-592.
[ ] Ravi Sethi and J. D. Ullman, "The Generation of Optimal Code
for Arithmetic Expressions," JACM 17:4 (), pp. 715-728.
Low-Level and Peephole Optimizations
[ ] W. J. Dally, "Micro-Optimization of Floating-Point Operations,"
Proceedings of the Third International Conference on Architec-
tural Support for Programming Languages and Operating Systems
(ASPLOS III), 3-6 April 1989, pp. 283-289.
[ ] J. Davidson, "A retargetable instruction reoranizer," in SIG-
PLAN Compiler Construction Conf., June 1986.
[ ] Jack W. Davidson and David B. Whalley, "Quick Compilers Using
Peephole Optimization," Software-Practice & Experience 19:1,
WILEY (January 1989), pp. 79-97.
[ ] C. Fraser and A. Wendt, "Integrating code generation and optim-
ization," in SIGPLAN Compiler Construction Conf., June 1986.
[ ] C. Fraser and A. Wendt, "Automatic generation of fast optimiz-
ing code generators," in SIGPLAN Conf. on Prog. Lang. Design
and Implementaion, June 1988.
[ ] P. B. Gibbons and S. S. Muchnick, "Efficient Instruction
Scheduling for a Pipelined Architecture," pp. 11-16 in ACM SIG-
PLAN 86 Symposium on Compiler Construction, June 1986.
[ ] J. Hennessy and T. Gross, "Postpass Code Optimization of Pipe-
line Constraints," ACM Transactions on Programming Languages
and Systems, July 1983, pp. 422-448.
[ ] A. S. Tanenbaum, H. van Staveren, and J. W. Stevenson, "Using
Peephole Optimization on Intermediate Code," ACM TOPLAS 3:1
(January 1982), pp. 21-36.
Compiler Kits
[ ] C. W. Fraser, "A Language for Writing Code Generators,"
Proceedings of the SIGPLAN '89 Conference on Programming
Language Design and Implementation, 21-23 June 1989, pp. 238-
245. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] H. Emmelmann, F.-W. Schroer, and R. Landwehr, "BEG - A Genera-
tor for Efficient Back Ends," Proceedings of the SIGPLAN '89
Conference on Programming Language Design and Implementation,
21-23 June 1989, pp. 227-237. In ACM SIGPLAN Notices 24:7
(July 1989).
[ ] A. S. Tanenbaum, H. van Staveren, E. G. Keizer, and J. W.
Stevenson, "A Practical Tool Kit for Making Portable Com-
pilers," CACM 26:9 (September 1983), pp. 654-660.
[ ] B. W. Leverett, R. G. G. Cattell, S. O. Hobbs, J. M. Newcomer,
A. H. Reiner, B. R. Schatz, and W. A. Wulf, "An Overview of the
Production-Quality Compiler-Compiler Project," Computer 13:8
(August 1980), pp. 38-49.
[ ] S. C. Johnson, "A Portable Compiler: Theory and Practice," ACM
Symposium on Principles of Programming Languages, January 1978.
[ ] M. E. Benitez and J. W. Davidson, "A Portable Global Optimizer
and Linker," Proceedings of the SIGPLAN '88 Conference on Pro-
gramming Language Design and Implementation, 22-24 June 1988,
pp. 329-338. In ACM SIGPLAN Notices 23:7.
Data Flow Analysis
[ ] A. V. Aho and J. D. Ullman, "Listings for Reducible Flow
Graphs," pp. 177-185 in 7th ACM Symposium on Theory of Comput-
ing, 1975.
[ ] F. E. Allen, "Control Flow Analysis," SIGPLAN notices 5:7, ACM
(1970), pp. 1-19.
[ ] F. Allen and J. Cocke, "A Program Data Flow Analysis Pro-
cedure," CACM 19:3, ACM (Mar 1976), pp. 137-147.
[ ] Michael Burke and Barbara G. Ryder, "Incremental Iterative Data
Flow Analysis Algorithms," 13170 (#58713), Computer Science
Department, IBM T. J. Watson Research Center, Yorktown Heights,
NY 10598, 9 October 1987.
[ ] D. Callahan, "The program summary graph and flow-sensitive
interprocedural data flow analysis," in SIGPLAN Conf. on Prog.
Lang. Design and Imple., June 1988..
[ ] R. Cartwright and M. Felleisen, "The Semantics of Program
Dependence," Proceedings of the SIGPLAN '89 Conference on Pro-
gramming Language Design and Implementation, 21-23 June 1989,
pp. 13-27. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] K. Culik, "Towards a Theory of Control-Flow and Data-Flow Algo-
rithms," Proceedings of the ICPP, IEEE, 1985, pp. 341-348.
[ ] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman,
and F. Kenneth Zadeck, "An Efficient Method of Computing Static
Single Assignment Form," CS-88-16, Brown University, Department
of Computer Science, Providence, Rhode Island 02912, October
1988. Also in 16th POPL, 1989.
[ ] J. Ferrante, K. J. Ottenstein, and J. D. Warren, "The Program
Dependence Graph and its Use in Optimization," ACM TOPLAS 9:3
(July 1987), pp. 319-349.
[ ] J. L. Gaudiot, "Methods for Handling Structures in Data-Flow
Systems," SIGARCH newsletter, Proceedings of the 12th Annual
Symposium on Computer Architecture 13:3, IEEE Computer Science
Press (June 1985), pp. 352-359.
[ ] S. L. Graham and M. Wegman, "A Fast and Usually Linear Algo-
rithm for Global Flow Analysis," pp. 22-34 in 2nd ACM Symposium
on Principls of Programming Languages, 1975.
[ ] W. Harrison, "Compiler analysis of the value ranges for vari-
ables," IEEE Transactions on Software Engineering SE-3:3 (May
1977).
[ ] M. S. Hecht, Flow Analysis of Computer Programs,, Elsevier,
Amsterdam, 1977.
[ ] Matthew S. Hecht and Jeffrey D. Ullman, "Flow Graph Reducibil-
ity," SIAM J. Comput. 1:2 (Jun 1972), pp. 188-202.
[ ] Matthew S. Hecht and Jeffrey D. Ullman, "A Simple Algorithm for
Global Data Flow Analysis," SIAM Journal on Computing 4:4, SIAM
(December 1975), pp. 519-532.
[ ] J. E. Hopcroft and J. D. Ullman, "An nlogn algorithm to dectect
reducible graphs," pp. 119-122 in Proc.6th Annyal Princeton
Conf on Informaiton Sciences and Systems.
[ ] Suneel Jain and Carol Thompson, "An Efficient Approach to Data
Flow Analysis in a Multiple Pass Global Optimizer," SIGPLAN
Notices: Proceedings of the SIGPLAN'88 Conference on Program-
ming Language Design and Implementation 23:7, ACM (July 1988),
pp. 154-163.
[ ] J. B. Kam and J. D. Ullman, "Monotone Data Flow Analysis Frame-
works," Acta Informatica 7 (1977), pp. 305-317.
[ ] K. Kennedy, "A Global Flow Analysis Algorithm," International
J. Comp Math 3:1 (), pp. 5-16.
[ ] K. Kennedy, "Node Listings Applied to Data Flow Analysis," pp.
10-21 in 2nd ACM Symposium on Principles of Programming
Languages, 1975.
[ ] Thomas Lengauer and Robert Endre Tarjan, "A Fast Algorithm for
Finding Dominators in a Flowgraph," TOPLAS 1:1, ACM (Jul 1979),
pp. 121-141.
[ ] E. Morel and C. Renvoise, "Global optimization by suppression
of partial redundancies," CACM 22:2 (Feb. 1979.).
[ ] E. W. Myers, "A Precise Inter-procedural Data Flow Algorithm,"
pp. 219-230 in Conference Record of the Eighth ACM Symposium on
Principles of Programming Languages, Jan. 1981.
[ ] T. Raeuchle, "Using Data Flow Analysis to Reduce the Cost of
Enforcing Consistency," Proceedings of the Seventh Interna-
tional Conference on Distributed Computing Systems, 21-25 Sep-
tember 1987, pp. 216-223.
[ ] B. Rosen, M. Wegman, and F, Zadeck, "Global value numbers and
redundant computations," in Fifteenth POPL, January 1988..
[ ] B. Ryder, "Incremental Data Flow Analysis," pp. 167-176 in
Conference Record of the Tenth ACM Symposium on Principles of
Programming Languages, Jan. 1983.
[ ] B. G. Ryder and M. C. Paull, "Elimination Algorithms for Data
Flow Analysis," ACM Computing Surveys 18:3 (September 1986),
pp. 277-316.
[ ] B. G. Ryder and M. C. Paull, "Incremental Data-Flow Analysis,"
ACM TOPLAS 10:1 (January 1988), pp. 1-50.
[ ] Barbara G. Ryder, "Incremental Data Flow Analysis Based on a
Unified Model of Elimination Algorithms," DCS-TR-117 (Also,
Ph.D. Thesis), Rutgers, 1982.
[ ] Barbara G. Ryder, "Incremental Data Flow Analysis," DCS-TR-120,
Rutgers, Sep 1982.
[ ] M. Schaefer, A Mathyematical Theory of Global Program Optimiza-
tion, Prentice-Hall, 1973?. Noted in AU Theory of Parsing ...
as ``to appear''.
[ ] Micha Sharir, "Structural Analysis: A New Approach To Flow
Analysis in Optimizing Compilers," Computer Languages 5, Per-
gammon Press Ltd (1980), pp. 141-153.
[ ] Olin Shivers, "Control Flow Analysis in Scheme," SIGPLAN
Notices: Proceedings of the SIGPLAN'88 Conference on Program-
ming Language Design and Implementation 23:7, ACM (July 1988),
pp. 164-174.
[ ] R. E. Tarjan, "A Unified Approach to Path Problems," JACM 28:3
(July 1981), pp. 577-593.
[ ] G. A. Venkatesh, "A Framework for Construction and Evaluation
of High-Level Specifications for Program Analysis Techniques,"
Proceedings of the SIGPLAN '89 Conference on Programming
Language Design and Implementation, 21-23 June 1989, pp. 1-12.
In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] M. Wegman and K. Zadeck,, "Constant Propagation with Condi-
tional Branches," pp. 291-299 in Conference Record of the
Twelfth ACM Syposium on Principles of Programming Languages,
Jan. 1985.
[ ] K. Zadeck, "Incremental Data Flow Analysis in a Structured Pro-
gram Editor," pp. 132-143 in ACM SIGPLAN 84 Symposium on Com-
piler Construction, June 1984.
Interprocedural Optimization
[ ] F. E. Allen, "Interprocedural Data Flow Analysis," Proceedins
of IFIP Congress 74, North-Holland (1974), pp. 398-402.
[ ] J. Ball, "Predicting the effects of optimization on a procedure
body," in SIGPLAN Compiler Construction Conference, August
1979.
[ ] M. Burke and R. Cytron, "Interprocedural Dependence Analysis
and Parallelization," Proceedings of the SIGPLAN'86 Symposium
on Compiler Construction, ACM, Jul 1986, pp. 162-175.
[ ] Michael Burke, "An Interval-Based Approach to Exhaustive and
Incremental Interprocedural Data Flow Analysis," 12702
(#56865), Computer Science Department, IBM T. J. Watson
Research Center, Yorktown Heights, NY 10598, 1 September 1987.
[ ] D. Callahan, K. D. Cooper,, K. Kennedy, and L. Torczon, "Inter-
procedural Constant Propagation," pp. 152-161 in ACM SIGPLAN 86
Symposium on Compiler Construction, June 1986.
[ ] D. Callahan and K. Kennedy,, "Analysis of Interprocedural Side
Effects in a Parallel Programming Environment," in Proceedings
of the First International Conference on Supercomputing, 1987.
[ ] K. D. Cooper, K. Kennedy, and L. Torczon, "The Impact of Inter-
procedural Analysis and Optimization on the Design of a
Software Development Environment," Proceedings of the ACM SIG-
PLAN 85 Symposium on Language Issues in Programming Environ-
ments, Seattle, Washington, 25-28 June 1985. In ACM SIGPLAN
Notices 20:7 (July 1985).
[ ] K. D. Cooper, K. Kennedy, and L. Torczon, "Interprocedural
Optimization: Eliminating Unnecessary Recompilation," Proceed-
ing of the SIGPLAN '86 Symposium on Compiler Construction, 25-
27 June 1986, pp. 58-67. In ACM SIGPLAN Notices 21:7 (July
1986).
[ ] K. Cooper and K. Kennedy, "Efficient Computation of Flow Insen-
sitive Interprocedural Summary Information," pp. 247-258 in ACM
SIGPLAN 84 Symposium on Compiler Construction, June 1984.
[ ] K. Cooper, K. Kennedy, and L. Torczon, "The Impact of Interpro-
cedure Analysis and Optimization in the Rn Programming Environ-
ment," ACM TOPLAS 8:4 (October 1986), pp. 491-523.
[ ] Keith D. Cooper and Ken Kennedy, "Interprocedural Side-Effect
Analysis in Linear Time," SIGPLAN Notices: Proceedings of the
SIGPLAN'88 Conference on Programming Language Design and Imple-
mentation 23:7, ACM (July 1988), pp. 57-66.
[ ] Susan Horwitz, Thomas Reps, and David Binkley, "Interprocedural
Slicing Using Dependence Graphs," SIGPLAN Notices: Proceedings
of the SIGPLAN'88 Conference on Programming Language Design and
Implementation 23:7, ACM (July 1988), pp. 35-46.
[ ] Christopher Alan Huson, "An In-Line Subroutine Expander for
Parafrase," Rpt. No. 82-1118, Univ. of Illinois at Urbana-
Champaign, Dept. of Computer Sci., Dec., 1982.
[ ] Zhiyuan Li and Pen-Chung Yew, "Interprocedural Analysis and
Program Restructuring for Parallel Programs," CSRD Report No.
720, Univ. of Illinois at Urbana-Champaign, Center for Super-
computing Res. & Dev..
[ ] Zhiyuan Li and Pen-Chung Yew, "Interprocedural Analysis for
Parallel Programs," Proc. of 1988 Int'l. Conf. on Parallel Pro-
cessing, St. Charles, IL, August 1988.
[ ] Zhiyuan Li and Pen-Chung Yew, "Efficient Interprocedural
Analysis for Program Parallelization and Restructuring.," SIG-
PLAN Notices 23:9, ACM Press (September 1988), pp. 85-99.
Proceedings of the ACM/SIGPLAN PPEALS 1988, July 19-21 1988.
[ ] Etienne Morel and Claude Renvoise, "Interprocedural Elimination
of Partial Redundancies," pp. 160-188 in Program Flow Analysis,
ed. Neil D. Jones, Prentice Hall, 1981.
[ ] S. Richardson and M. Ganapathi, "Interprocedural Analysis - A
Bibliography," ACM SIGPLAN Notices 22:6 (June 1987), pp. 12-17.
[ ] S. Richardson and M. Ganapathi , "Code Optimization Across
Procedures ," Computer 22:2 (February 1989), pp. 42-50 .
[ ] Barbara G. Ryder, "A Survey of Interprocedural Data Flow
Analysis Techniques," DCS-TR-85, Rutgers, Dec 1979.
[ ] R. Scheifler, "An analysis of inline substitution for a struc-
tured programming language," CACM 20:9 (Sept. 1977.).
[ ] Micha Sharir and Amir Pnueli, "Two Approaches to Interpro-
cedural Data Flow Analysis," pp. 189-233 in Program Flow
Analysis, ed. Neil D. Jones, Prentice Hall, 1981.
[ ] Remi Triolet, "Interprocedural Analysis for Program Restructur-
ing with Parafrase," CSRD Rpt. No. 538, Univ. of Illinois at
Urbana-Champaign, Center for Supercomputing Res. & Dev., Aug.,
1986.
Register Allocation
[ ] J. C. Beatty, "Register Assignment Algorithm for Generation of
Highly Optimized Object Code," IBM J. Res. Devel, , pp. 20-39.
[ ] J. C. Beatty, "A Global Register Assigment Algorithm," pp. 65-
68 in Design and Optimization of Compilers, ed. R. Rustin,
Prentice-Hall, 1972.
[ ] D. Bernstein, M. Golumbic, Y. Mansour, R. Pinter, D. Goldin, H.
Drawczyk, and I. Nahshon, "Spill Code Minimization Techniques
for Optimizing Compilers," Proceedings of the SIGPLAN '89
Conference on Programming Language Design and Implementation,
21-23 June 1989, pp. 258-263. In ACM SIGPLAN Notices 24:7
(July 1989).
[ ] P. Briggs, K. D. Cooper, K. Kennedy, and L. Torczon, "Coloring
Heuristics for Register Allocation," Proceedings of the SIGPLAN
'89 Conference on Programming Language Design and Implementa-
tion, 21-23 June 1989, pp. 275-284. In ACM SIGPLAN Notices
24:7 (July 1989).
[ ] C.-H. Chi and H. Dietz, "Unified Management of Registers and
Cache Using Liveness and Cache Bypass," Proceedings of the SIG-
PLAN '89 Conference on Programming Language Design and Imple-
mentation, 21-23 June 1989, pp. 344-355. In ACM SIGPLAN
Notices 24:7 (July 1989).
[ ] Fred C. Chow, "Minimizing Register Usage Penalty at Procedure
Calls," SIGPLAN Notices: Proceedings of the SIGPLAN'88 Confer-
ence on Programming Language Design and Implementation 23:7,
ACM (July 1988).
[ ] R. Gupta, M. L. Soffa, and T. Steele, "Register Allocation Via
Clique Separators," Proceedings of the SIGPLAN '89 Conference
on Programming Language Design and Implementation, 21-23 June
1989, pp. 264-274. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] W. C. Hsu, C. N. Fischer, and J. R. Goodman, "On the Minimiza-
tion of Loads and Stores in Local Register Allocation," IEEE
Transactions on Software Engineering 15:10 (October 1989), pp.
1252-1260.
[ ] P. A. Karger, "Using Registers to Optimize Cross-Domain Call
Performance," Proceedings of the Third International Conference
on Architectural Support for Programming Languages and Operat-
ing Systems (ASPLOS III), 3-6 April 1989, pp. 194-204.
[ ] D. Wall, "Global register allocation at link time," in SIGPLAN
Compiler Construction Conf, June 1986..
Alias Detection
[ ] B. Alpern, M. Wegman, and F. Zadeck,, "Detecting equality of
variables in programs," in Fifteenth POPL, January 1988.
[ ] Keith D. Cooper, "Analyzing Aliases of Reference Formal Parame-
ters," Conference Record of the Twelfth POPL, ACM SIGACT SIG-
PLAN, January 1985, pp. 281-290.
[ ] S. Horwitz, P. Pfeiffer, and T. Reps, "Dependence Analysis for
Pointer Variables," Proceedings of the SIGPLAN '89 Conference
on Programming Language Design and Implementation, 21-23 June
1989, pp. 28-40. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] Anne Denise Neyrinck, "Static Analysis of Aliases and Side
Effects in Higher-Order Languages," 88-896, Cornell University,
Department of Computer Science, Ithaca, NY 14853-7501, February
1988. Ph.D. Thesis. January 1988 is also given as a date..
[ ] W. Weihl, "Interprocedural Data Flow Analysis in the Presence
of Pointers, Procedure Variables, and Label Variables,"
Proceedings of the 7th Symposium on Principles of Programming
Languages, January 1980, pp. 83-94.
Vectorization and Parallelization
[ ] Alexander Aiken, "Compaction-Based Parallelization," Ph.D.
Thesis, TR 88-922, Department of Computer Science, Cornell
University, Ithaca, NY 14853-7501, June 1988.
[ ] Alexander Aiken and Alexandru Nicolau, "Optimal Loop Paralleli-
zation," SIGPLAN Notices: Proceedings of the SIGPLAN'88 Confer-
ence on Programming Language Design and Implementation 23:7,
ACM (July 1988), pp. 308-317.
[ ] Eugene Albert, Kathleen Knobe, Joan D. Lukas, and Guy L. Steele
Jr., "Compiling Fortran 8x Array Features for the Connection
Machine Computer System," SIGPLAN Notices 23:9, ACM Press (Sep-
tember 1988), pp. 42-56. Proceedings of the ACM/SIGPLAN PPEALS
1988, July 19-21 1988.
[ ] Fran Allen, Michael Burke, Philippe Charles, Ron Cytron, and
Jeanne Ferrante, "An Overview of the PTRAN Analysis System for
Multiprocessing," 13115 (#56866), Computer Science Department,
IBM T. J. Watson Research Center, Yorktown Heights, NY 10598,
29 September 1987.
[ ] J. R. Allen and K. Kennedy, "PFC: A program to convert Fortran
to parallel form," MASC-TR82-6, Rice University.
[ ] J. R. Allen and K. Kennedy, "Automatic Loop Interchange," pp.
233-246 in Proc. of the ACM SIGPLAN Symposium on Compiler Con-
struction, Montreal, 1984.
[ ] J. R. Allen and K. Kennedy, "Automatic Translation of Fortran
Programs to Vector Form," Transactions on Programming Languages
and Systems, October 1987.
[ ] J. R. Allen and Ken Kennedy, "PFC: A Program to Convert Fortran
to Parallel Form," in Proceedings IBM Conf. Parallel Computers
in Scientific Computations, Rome, 1982. , K. Hwang ed., IEEE
Computer Society Press, Silver Spring, MD 1984"" Also in
"Supercomputers: Design and Applications", K. Hwang ed., IEEE
Computer Society Press, Silver Spring, MD 1984.
[ ] J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren,
"Conversion of Control Dependence to Data Dependence," Confer-
ence Record of the Tenth POPL, ACM, Jan 1983, pp. 177-189.
[ ] Randy Allen, David Callahan, and Ken Kennedy, "Automatic Decom-
position of Scientific Programs for Parallel Execution,"
Conference Record of the Fourteenth POPL, ACM, Jan 1987, pp.
63-76.
[ ] Randy Allen and Steve Johnson, "Compiling C for Vectorization,
Parallelization, and Inline Expansion," SIGPLAN Notices:
Proceedings of the SIGPLAN'88 Conference on Programming
Language Design and Implementation 23:7, ACM (July 1988), pp.
241-249.
[ ] V. Balasundaram and K. Kennedy, "A Technique for Summarizing
Data Access and Its Use in Parallelism Enhancing Transforma-
tions," Proceedings of the SIGPLAN '89 Conference on Program-
ming Language Design and Implementation, 21-23 June 1989, pp.
41-53. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] U. Banerjee, "Direct Parallelization of Call Statements," Rept
576, Center for Supercomputer Research and Development, 1985.
[ ] U. Banerjee, S. C. Chen, D. J Kuck, and R. A. Towle, "Time and
Parallel Processor Bounds for Fortran-like Loops," IEEE Trans
Comput C-28:9 (1979), pp. 660-670.
[ ] Alan M. Baum and Donald J. McMillan, Automated Parallelization
of Serial Simulations for Hypercube Parallel Processors, Com-
puter Science Department, General Motors Research Laboratories,
Warren, Michigan 48090, 24 January 1989.
[ ] Michael Burke, Ron Cytron, Jeanne Ferrante, Wilson Hsieh, Vivek
Sarkar, and David Shields, "Automatic Discovery of Parallelism:
A Tool and and Experiment (Extended Abstract)," SIGPLAN Notices
23:9, ACM Press (September 1988), pp. 77-84. Proceedings of
the ACM/SIGPLAN PPEALS 1988, July 19-21 1988.
[ ] Alan Carle, Keith D. Cooper, Robert T. Hood, Ken Kennedy, Linda
Torczon, and Scott K. Warren, "A Practical Environment for
Scientific Programming," Computer 20:11, IEEE (Nov 1987), pp.
75-89.
[ ] R. Cytron, M. Hind, and W. Hsieh, "Automatic Generation of DAG
Parallelism," Proceedings of the SIGPLAN '89 Conference on Pro-
gramming Language Design and Implementation, 21-23 June 1989,
pp. 54-68. In ACM SIGPLAN Notices 24:7 (July 1989).
[ ] Ronald Gary Cytron, "Improved Compilation Methods for Multipro-
cessors," UIUCDCS-R-82-1088, University of Illinois at Urbana-
Champaign, Urbana, IL 61801-2987, May 1982. M.Sc. Thesis.
[ ] Erik H. D'Hollander, "Computer Aided Dataflow Analysis for the
Conversion of Sequential Programs into Parallel Form," pp.
75-102 in Algorithms and Applications on Vector and Parallel
Computers, ed. H. A. van der Vorst, Elsevier Science Publishers
B. V. (North-Holland), 1987.
[ ] Henry G. Dietz, "Finding Large-Grain Parallelism In Loops With
Serial Control Dependencies," Proceedings of the 1988 Interna-
tional Conference on Parallel Processing, Volume II, Software,
Penn State, August 1988, pp. 114-121.
[ ] Jeanne Ferrante and Mary Mace, "On Linearizing Parallel Code,"
Conference Record of the Twelfth POPL, Volume II, Software, ACM
SIGACT SIGPLAN, January 1985, pp. 179-190.
[ ] Jeanne Ferrante and Karl J. Ottenstein, "A Program Form Based
on Data Dependency in Predicate Regions," Conference Record of
the Tenth POPL, Volume II, Software, ACM, Jan 1983, pp.
217-236.
[ ] C. C. Foster and E. M. Riseman, "The Inhibition of Potential
Parallelism by Conditional Jumps," IEEE Transactions on Comput-
ers 21, Volume II, Software:12, IEEE (1972), pp. 1405-1411.
[ ] Harlan E Husmann, David J. Kuck, and David A. Padua, "Automatic
Compound Function Definition for Multiprocessors," Proceedings
of the 1988 International Conference on Parallel Processing,
Volume II, Software, Penn State, August 1988, pp. 33-41.
[ ] Alan H. Karp, "Programming for Parallelism," Computer 20,
Volume II, Software:5, IEEE (May 1987), pp. 43-57.
[ ] Ken Kennedy, "Automatic translation of Fortran programs to vec-
tor form," 476 029 4, Rice U., Oct 1980.
[ ] Youji Kohda and Jiro Tanaka, "Deriving a Compilation Method for
Parallel Logic Machines," TR 350, ICOT Research Center, Tokyo,
March 1988.
[ ] D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe,
"Dependence Graphs and Compiler Optimizations," Conference
Record of the Eighth POPL, Volume II, Software, ACM, Jan 1981,
pp. 207-218.
[ ] D. Kuck, Y. Muraoka, and S.-C. Chen, "On the number of opera-
tions simultaneously executable in Fortran-like programs and
their resulting speedup," IEEE Transaction on Computers C-21,
Volume II, Software:12 (Dec 1972), pp. 1293-1310.
[ ] David J. Kuck, "Parallel Processing of Ordinary Programs,"
UIUCDCS-R-75-767, University of Illinois at Urbana-Champaign
Dept. of C. Sc., November 1975.
[ ] David J. Kuck, "High Speed Multiprocessing and Compilation
Techniques," IEEE Transactions on Computers, Volume II,
Software, IEEE, 1980, pp. 763-776.
[ ] Monica S. Lam, A Systolic Array Optimizing Compiler, Kluwer
Academic Publishers, 1989.
[ ] Gyungho Lee, "Automatic Restructuring of Conditional Cyclic
Loops," Proceedings of the 1988 International Conference on
Parallel Processing, Volume II, Software, Penn State, August
1988, pp. 42-45.
[ ] Alexandru Nicolau, "Uniform Parallelism Extraction in Ordinary
Programs," Proceedings of the ICPP, Volume II, Software, IEEE,
1985, pp. 614-618.
[ ] Alexandru Nicolau, "Run-Time Disambiguation: Coping with Stati-
cally Unpredictable Dependencies," Transactions on Computers
38, Volume II, Software:5, IEEE (May 1989), pp. 663-678.
[ ] K. J. Ottenstein, "A Brief Survey of Implicit Parallelism
Detection," pp. 93-122 in Parallel MIMD Computation: HEP Super-
computer and Its Applications, ed. Janusz Kowalik, MIT Press,
1985.
[ ] D. Padua and M. J. Wolfe, "Advanced Compiler Optimizations for
Supercomputers," CACM 29, Volume II, Software:12 (Dec 1986),
pp. 1184-1201. Big bibliography.
[ ] Constantine D. Polychronopoulos, "Loop Coalescing: A Compiler
Transformation for Parallel Machines," Proceedings of the ICPP,
Volume II, Software, IEEE, 1987, pp. 235-242.
[ ] Constantine D. Polychronopoulos, "Compiler Optimizations for
Enhancing Parallelism and Their Impact on Architecture Design,"
Transactions on Computers 37, Volume II, Software:8, IEEE (Aug
1988), pp. 991-1004.
[ ] A. Rogers and K. Pingali, "Process Decomposition Through Local-
ity of Reference," Proceedings of the SIGPLAN '89 Conference on
Programming Language Design and Implementation, Volume II,
Software, 21-23 June 1989, pp. 69-80. In ACM SIGPLAN Notices
24:7 (July 1989).
[ ] Vivek Sarkar, "Partitioning and Scheduling Parallel Programs
for Execution on Multiprocessors," CSL-TR-87-328, Computer Sys-
tems Laboratory, Stanford University, April 1987. Ph.D.
Thesis.
[ ] Vivek Sarkar and J. Hennessy, "Compile-time Partitioning and
Scheduling of Parallel Programs," Proceedings of the SIGPLAN'86
Symposium on Compiler Construction, Volume II, Software, ACM,
Jul 1986, pp. 17-26.
[ ] Weijia Shang and Jose A. B. Fortes, "On The Independent Parti-
tioning of Algorithms With Uniform Data Dependencies," Proceed-
ings of the 1988 International Conference on Parallel Process-
ing, Volume II, Software, Penn State, August 1988, pp. 26-33.
[ ] Kevin Smith and William F. Appelbe, "PAT -- An Interactive For-
tran Parallelizing Assistant Tool," Proceedings of 1988 ICPP 2,
Volume II, Software, The Pennsylvania State University Press
(15-19 August 1988), pp. 58-62.
[ ] G. S. Tjaden and M. J. Flynn, "Detection and parallel execution
of independent instructions," IEEE Transactions on Computers
21, Volume II, Software:10 (Oct 1970), pp. 889-895.
[ ] R. Triolet, F. Irigoin, and P. Feautrier, "Direct Paralleliza-
tion of Call Statements," Proc. of the SIGPLAN 86 Symp. on Com-
piler Construction, SIGPLAN No. 21, Volume II, Software, July,
1986, pp. 176-185.
[ ] Remi Triolet, Paul Feautrier, and Francois Irigoin, "Automatic
Parallelizations of Fortran Programs in the Presence of Pro-
cedure Calls," European Symposium on Programming Languages,
Volume II, Software, 1986.
[ ] M. J. Wolfe, "Optimizing Supercompilers for Supercomputers,"
Ph. D. Dissertation, October 1982.
[ ] Michael J. Wolfe, "Techniques for Improving the Inherent Paral-
lelism in Programs," UIUCDCS-R-78-929, University of Illinois
at Urbana-Champaign, Dept. of Comp. Sc., Jul 1978. M.Sc.
Thesis.
[ ] Michael Wolfe and Utpal Banerjee, "Data Dependence and Its
Application to Parallel Processing," International Journal of
Parallel Programming 16, Volume II, Software:2, Plenum Press
(1987), pp. 137-178.
[ ] Yaron Wolfstahl, "Mapping parallel programs to multiprocessors:
A dynamic approach," Parallel Computing 10, Volume II,
Software, North-Holland (1989), pp. 45-50.
[ ] Youfeng Wu, "Parallelizing WHILE Loops," 87-10-1, Oregon State
University, Computer Science Department, Corvallis, Oregon,
undated, perhaps 1987.
Program Transformations
[ ] F. E. Allen and J. Cocke, "A Catalogue of Optimizing Transfor-
mations," pp. 1-30. in Design and Optimization of Compilers,
ed. R. Rustin, Prentice-Hall, 1971.
[ ] Lee Badger and Mark Weiser, "Minimizing Communication for Syn-
chronizing Parallel Dataflow Programs," Proceedings of the 1988
International Conference on Parallel Processing, Volume II,
Software, Penn State, August 1988, pp. 122-126.
[ ] Pradip Bose, "Heuristic Rule-Based Program Transformations for
Enhanced Vectorization," Proceedings of 1988 ICPP 2, Volume II,
Software, The Pennsylvania State University Press (15-19 August
1988), pp. 63-66.
[ ] R. Cytron, A. Lowry, and K. Zadeck, "Code motion of control
structures in high-level languages," in Thirteenth POPL, Janu-
ary 1986..
[ ] James R. Larus and Paul N. Hilfinger, "Restructuring Lisp Pro-
grams for Concurrent Execution," SIGPLAN Notices 23, Volume II,
Software:9, ACM Press (September 1988), pp. 100-110. Proceed-
ings of the ACM/SIGPLAN PPEALS 1988, July 19-21 1988.
[ ] D. B. Loveman, "Program Improvement by Source-to-Source
Transformation," JACM 20, Volume II, Software:1 (Jan. 1977),
pp. 121-145.
[ ] H. R. A. Strong, A. Maggiolo-Schettini, and B. A. Rosen, "Recu-
sion Structure Simplification," SIAM J. Comput 4, Volume II,
Software:3 (1975), pp. 307-320.
Debugging and Optimization
[ ] P. Fritzson, "A Systematic Approach to Advanced Debugging
through Incremental Compilation," pp. 130-139 in ACM
SIGSOFT/SIGPLAN Software Engineering Symposium on High-Level
Debugging, March 1983.
[ ] J. Hennessy, "Symbolic Debugging of Optimized Code," ACM Tran-
sactions on Programming Languages and Systems 4, Volume II,
Software:3 (July 1982), pp. 323-344.
[ ] P. T. Zellweger, "An Interactive High-Level Debugger for
Control-Flow Optimized Programs," pp. 159-171 in ACM
SIGSOFT/SIGPLAN Software EngineeringSymposium on High-Level
Debugging, March 1983.
[ ] P. T. Zellweger, "Interactive Source-Level Debugging for Optim-
ized Programs," Technical report from somewhere, May 1984.
RISC Compilers
[ ] F. Chow, M. Himelstein, E. Killian, and L. Weber, "Engineering
a RISC compiler system," pp. 132-137. in Digest of Papers of
the Thirtyfirst IEEE Computer Society International Conference,
IEEE, Feb 1986.
[ ] C. E. Gimarc and V. M. Milutinovic, "A Survey of RISC Proces-
sors and Computers of the Mid-1980s," Computer 20, Volume II,
Software:9 (September 1987), pp. 59-69.
[ ] T. R. Gross, "Code Optimization of Pipeline Constraints,"
Ph. D. thesis, Stanford University, August 1983.
[ ] J. L. Hennessy and T. R. Gross, "Postpass Code Optimization of
Pipeline Constraints," ACM TOPLAS 5, Volume II, Software:3
(July 1983).
[ ] J. R. Larus and R. N. Hilfinger, "Register Allocation in the
SPUR Lisp Compiler," pp. 255-263. in ACM SIGPLAN 86 Symposium
on Compiler Construction, June 1986.
[ ] J. W. Rymarcyk, "Coding Guidelines for Pipelined Processors,"
ACM 0-89791-066-4, International Business Machines.
[ ] P. Steenkiste and J. Hennessy, "Lisp on a Reduced-Instruction-
Set Processor: Characterization and Optimization," Computer 21,
Volume II, Software:7 (July 1988), pp. 34-45.
[ ] David W. Wall, "Register Windows vs. Register Allocation," SIG-
PLAN Notices: Proceedings of the SIGPLAN'88 Conference on Pro-
gramming Language Design and Implementation 23, Volume II,
Software:7, ACM (July 1988), pp. 67-78.
VLIW Compilers
[ ] Robert P. Colwell, Robert P. Nix, John J. O'Donnell, David B.
Papworth, and Paul K. Rodman, "A VLIW Architecture for a Trace
Scheduling Compiler," Transactions on Computers 37, Volume II,
Software:8, IEEE (Aug 1988), pp. 967-979.
[ ] John R. Ellis, "BULLDOG: A compiler for VLIW Architectures,"
YALEU/DCS-RR-364, Yale, February 1985. Also an ACM dis-
tinguished thesis, published by MIT Press.
[ ] Joseph A. Fisher, "Trace Scheduling: A technique for global
microcode compaction," IEEE Transactions on Computers C-30,
Volume II, Software:7 (Jul 1981), pp. 478-490.
[ ] Monica Lam, "Software Pipelining: An Effective Scheduling Tech-
nique for VLIW Machines," SIGPLAN Notices: Proceedings of the
SIGPLAN'88 Conference on Programming Language Design and Imple-
mentation 23, Volume II, Software:7, ACM (July 1988), pp.
318-328.
[ ] Alexandru Nicolau, "Parallelism, Memory Anti-Aliasing And
Correctness for Trace Scheduling Algorithms," YALE/DCS/RR-374,
Yale, March 1985.
[ ] Alexandru Nicolau, "Percolation Scheduling: A Parallel Compila-
tion Technique," TR-85-678, Cornell University, May 1985.
--
Michael L. Scott
Computer Science Dept. (716) 275-7745, 5671
University of Rochester scott@cs.rochester.edu
Rochester, NY 14627 ...!rochester!scott
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.