home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compiler / 1293 < prev    next >
Encoding:
Text File  |  1992-07-30  |  9.4 KB  |  277 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: rjohnson@cs.cornell.edu (Richard C. Johnson)
  4. Subject: phase-ordering optimizations (SUMMARY)
  5. Reply-To: rjohnson@cs.cornell.edu (Richard C. Johnson)
  6. Organization: Compilers Central
  7. Date: Thu, 30 Jul 1992 20:34:42 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-07-114@comp.compilers>
  10. Keywords: optimize, summary, bibliography
  11. Sender: compilers-sender@iecc.cambridge.ma.us
  12. Lines: 263
  13.  
  14. This is a summary of replies to my comp.compiler request for information
  15. on phase ordering and integrating optimizations.  Many thanks to all who
  16. sent references/comments!
  17.  
  18. My original posting:
  19.    I'm looking for references to work on interactions between various
  20.    compiler optimizations.  Specifically, I'd be interested in references to
  21.    papers on the ordering of optimization phases, integration of optimization
  22.    phases to eliminate the need for ordering, and cooperation between
  23.    optimizations and scheduling & resource allocation.  I'm familiar with
  24.    Joshi & Dhamdhere's work on combining strengh reduction and code hoisting,
  25.    with Goodman & Hsu's algorithm for combining reg.allocation and code
  26.    scheduling in basic blocks, and with Ruttenberg and Freundenberger's work
  27.    on combining instruction scheduling and global register allocation.
  28.  
  29. References to the papers I mentioned:
  30.  
  31. @article{    JD82a:ijcm,
  32.    author    = "S. M. Joshi and D. M. Dhamdhere",
  33.    title    = "A Composite Hoisting--Strength Reduction Transformation
  34.             for Global Program Optimization (Part I)",
  35.    journal    = "Int. J. of Computer Math",
  36.    pages    = {22-41},
  37.    year        = 1982
  38. }
  39.  
  40. @article{    JD82b:ijcm,
  41.    author    = "S. M. Joshi and D. M. Dhamdhere",
  42.    title    = "A Composite Hoisting--Strength Reduction Transformation
  43.             for Global Program Optimization (Part II)",
  44.    journal    = "Int. J. of Computer Math",
  45.    pages    = {111-126},
  46.    year        = 1982
  47. }
  48.  
  49. @inproceedings{    GH88:ics,
  50.    author    = "James R. Goodman and {Wei-Chung} Hsu",
  51.    title    = "Code Scheduling and Register Allocation in Large
  52.             Basic Blocks",
  53.    booktitle    = "Proc. of the 1988 Int. Conference on Supercomputing",
  54.    address    = "St. Malo, France",
  55.    note        = "Published by SIGARCH Computer Architecture News",
  56.    month    = "July 4--8, "
  57.    year        = 1988,
  58.    pages    = {442-452},
  59. }
  60.  
  61. @unpublished{    RF91:unpub,
  62.    author    = "John C. Ruttenberg and Stefan M. Freudenberger",
  63.    title    = "Phase Ordering of Register Allocation
  64.                 and Instruction Scheduling",
  65.    booktitle    = "Workshop on Code Generation -- Concepts, Tools,
  66.            Techniques",
  67.    month    = apr,
  68.    year        = 1991,
  69. }
  70. [ I do not know whether the proceedings of this workshop were ever published.
  71.   The workshop was somewhere in Germany in 1991. ]
  72.  
  73. ------------------------------------------------------------------------------
  74. Eliot Moss (moss%ibis@cs.umass.edu), Steve Walk (srw@ihlpv.att.com), and
  75. Martin Meyer <martin@uni-paderborn.de> suggested the following paper:
  76.  
  77. @inproceedings{    Whitfield&Soffa1990,
  78.    author    = "Debbie Whitfield and Mary Lou Soffa",
  79.    title    = "An Approach to Ordering Optimizing Transformations",
  80.    booktitle    = "Second {ACM} {SIGPLAN} Symposium on Principles and
  81.             Practice of Parallel Programming",
  82.    address    = "Seattle, Washington",
  83.    month    = "March 14--16, ",
  84.    year        = 1990,
  85.    pages    = {137-147},
  86.    note        = "Published as {ACM SIGPLAN} Notices 25(3)",
  87. }
  88.  
  89. -------------------------------------------------------------------------------
  90. from anton@mips.complang.tuwien.ac.at (Anton Martin Ertl):
  91.  
  92. The following article extends Goodman&Hsu's Integrated Prepass
  93. Scheduling to colouring global register allocation and introduces
  94. another algorithm:
  95.  
  96. @InProceedings{bradlee+91asplos,
  97.   author =     "David G. Bradlee and Susan J. Eggers and Robert R. Henry",
  98.   title =     "Integrating Register Allocation and Instruction
  99.          Scheduling for {RISCs}",
  100.   booktitle =     asplos,
  101.   year =     "1991",
  102.   pages =     "122--131"
  103. }
  104.  
  105. One of the claimned advantages of the Davidson&Fraser approach to Code
  106. generation is the ability to apply the phases in arbitrary order (and
  107. repeatedly), solving many phase ordering problems. I find in my
  108. bibliography the following references. You probably should read
  109. benitez&davidson88 first, which presents a nice overview of the approach.
  110.  
  111. @inproceedings(davidson86,
  112. author="Jack W. Davidson",
  113. title="A Retargetable Instruction Reorganizer",
  114. booktitle="Proceedings of the SIGPLAN '86 Symposium on Compiler
  115. Construction",
  116. year="1986",
  117. pages="234--241"
  118. )
  119.  
  120. @Article{davidson&fraser84,
  121.   author =     "Jack W. Davidson and Christopher W. Fraser",
  122.   title =     "Code Selection through Object Code Optimization",
  123.   journal =     toplas,
  124.   year =     "1984",
  125.   volume =     "6",
  126.   number =     "4",
  127.   pages =     "505--526",
  128.   month =     oct
  129. }
  130.  
  131. @InProceedings{benitez&davidson88,
  132.   author =     "Manuel E. Benitez and Jack W. Davidson",
  133.   title =     "A Portable Global Optimizer and Linker",
  134.   booktitle =     "Proceedings of the SIGPLAN '88 Conference on
  135.          Programming Language Design and Implementation",
  136.   year =     "1988",
  137.   pages =     "329--338"
  138. }
  139.  
  140. @InProceedings{fraser&wendt88,
  141.   author =     "Christopher W. Fraser and Alan L. Wendt",
  142.   title =     "Automatic Generation of Fast Optimizing Code Generators",
  143.   booktitle =     "Proceedings of the SIGPLAN '88 Conference on
  144.          Programming Language Design and Implementation",
  145.   year =     "1988",
  146.   pages =     "79--84"
  147. }
  148.  
  149. Coagulation was developped for solving the
  150. code-selection/register-allocation phase ordering problem. It's
  151. similar to Ruttenberg&Freudenberger's work.
  152.  
  153. @InProceedings{morris91,
  154.   author =     "W. G. Morris",
  155.   title =     "{CCG}: A Prototype Coagulating Code Generator",
  156.   booktitle =     "Proceedings of the SIGPLAN '91 Conference on
  157.          Programming Language Design and Implementation",
  158.   year =     "1991",
  159.   pages =     "45--58",
  160.   address =     "Toronto",
  161.   month =     jun
  162. }
  163.  
  164. The original article on coagulation is in the SIGPLAN '84 Proceedings.
  165.  
  166. - anton
  167.  
  168. ---
  169. The original coagulation paper is:
  170. @inproceedings{    Kar84:socc,
  171.    author    = "Michael Karr",
  172.    title    = "Code Generation by Coagulation",
  173.    booktitle    = "Proc. 1984 SIGPLAN Symposium on Compiler Construction",
  174.    address    = "Montreal, Canada"
  175.    month    = "June 17--22, ",
  176.    year        = 1984,
  177.    pages    = {1-12},
  178.    note        = "Published as ACM SIGPLAN Notices 19(6)"
  179. }
  180.  
  181. I also found the following paper by Fraser&Wendt:
  182. @inproceedings{    FW86:socc,
  183.    author    = "Christopher W. Fraser and Alan L. Wendt",
  184.    title    = "Integrating Code Generation and Optimization",
  185.    booktitle    = "Proc. of the 1986 SIGPLAN Symp. on Compiler Construction",
  186.    address    = "Palo Alto, California",
  187.    month    = "June 25--27, ",
  188.    year        = 1986,
  189.    pages    = {242-248},
  190.    note        = "Published as ACM SIGPLAN Notices 21(7)",
  191. }
  192.  
  193. -------------------------------------------------------------------------------
  194. Reply-To: berson@cs.pitt.edu (David A. Berson)
  195.  
  196. > Specifically, I'd be interested in references to
  197. > papers on the ordering of optimization phases, integration of optimization
  198. > phases to eliminate the need for ordering, and cooperation between
  199. > optimizations and scheduling & resource allocation.
  200.  
  201. How about the following?
  202. %A Deborah Whitfield
  203. %A Mary Lou Soffa
  204. %T Automatic Generation of Global Optimizers
  205. %P 120-129
  206. %J PROC SIGPLAN '91 CONF PLDI
  207. %D JUN 26-28, 1991
  208. %C Toronto, Ontario, Canada
  209.  
  210. %A Deborah Lynn Whitfield
  211. %T A Unifying Framework For Optimizing Transformations
  212. %I Ph.D. Dissertation, University of Pittsburgh
  213. %R TECH REPORT 91-24
  214. %D 1991
  215.  
  216. This looks at how different optimizations can impact each other and then
  217. suggests orderings.  The paper is taken from the dissertation.
  218.  
  219. -------------------------------------------------------------------------------
  220. Reply-To: Arild Skjolsvold <arilds@microsoft.com>
  221.  
  222. A book called "Register Allocation in Optimizing Compilers" discusses
  223. the phase ordering problem. This book describes the PQCC project, so
  224. other papers about that project is relevant as well I'd guess.  The
  225. author of the book?? I can't remember, sorry...
  226.  
  227. -arild
  228.  
  229. ---
  230. The book reference is:
  231. @book{        Lev83:book,
  232.    author    = "Bruce W. Leverett",
  233.    title    = "Register Allocation in Optimizing Compilers",
  234.    year        = 1983,
  235.    publisher    = "UMI Research Press",
  236.    address    = "Ann Arbor, Mich."
  237. }
  238.  
  239. -------------------------------------------------------------------------------
  240. Reply-To: Martin Meyer <martin@uni-paderborn.de>
  241.  
  242. In addition to Whitfield&Soffa1990, Martin suggested:
  243.  
  244. %A Deborah Whitfield
  245. %T A Unifying Framework for Optimizing Transformations
  246. %J Technical Report 91-24
  247. %I University of Pittsburgh, Pennsylvania
  248.  
  249. It describes dependences, enabling and disabling conditions for 
  250. various optimizing transformations (standard transformations as well
  251. as loop transformations).
  252.  
  253. Hope, it helps.
  254.  
  255. - martin
  256.  
  257. -------------------------------------------------------------------------------
  258. Reply-To: loegel@redfox.ssc.gov (George Loegel)
  259.  
  260. Giegerich, R. "Logic Specification of Code Generation Techniques",
  261. Lecture Notes in Computer Science No. 217, pp. 96-111, 1985
  262.  
  263. In this paper each kind of optimization is described as an algebraic
  264. transformation and combining optimizations is simply a matter of
  265. sequencing the transformations.  Giegerich describes these algebras in
  266. PROLOG.  Code generation takes place by satisfying a set of conditions
  267. between the input to the code generator and the target machine.
  268. ---
  269. [ LNCS #217 title is "Programs as Data Objects" ]
  270.  
  271. -------------------------------------------------------------------------------
  272. Richard Johnson
  273. rjohnson@cs.cornell.edu
  274. -- 
  275. Send compilers articles to compilers@iecc.cambridge.ma.us or
  276. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  277.